C code free from bitwise operation O(n) time O(1) space


  • 0
    Z

    I was using the partition technique similar to what we have in Randomized Quick Sort.

    The key idea is that if there are 3k elements that is less than or equal to the pivot, then the single number must be larger than the pivot, otherwise there would be 3k+1 elements.

    Only that in quick sort we have T(n)=2T(n/2)+O(n).
    Here we have T(n)=T(n/2)+O(n). Mathematically, it should be T(n)=O(n).

    int partition(int *nums, int l, int r){
        int i = l,j = l;
        int t = l + rand()%(r-l+1);
        int tmp,p;
        p = nums[t];
        nums[t] = nums[r];
        nums[r] = p;
        
        for ( ; i <= r; i++){
            if (nums[i] <= p ){
                tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }return j;
    }
    
    int singleNumber(int* nums, int numsSize) {
        int i = 0, j = numsSize-1;
        int par;
        while(i<j){
            par = partition(nums,i,j);
            if (par%3 == 0){
                i = par;
            } else j = par-1;
        }
        return nums[i];
    }
    

  • 0
    A

    @zhangc This is not O(n) time, this is O(nlogn) time on average. In worst case, this is O(n^2) time.


  • 0
    Z

    O(nlogn) is QuickSort, and it recursively call it self twice.

    My method it equivalent to recursively calling itself only once, the the expected runtime is O(n).

    It's true though that the worst case is O(n^2). But since the it's a randomized one, I prefer talking about expected runtime or average case.


  • 0
    A

    @zhangc I told you even average is still O(nlogn). Think about it. Every time you call sort, you have to iterate through all elements in the array supplied in the argument. So let's say the size of the array is 10,000, how many times do you have to call the sort? On average, about log(10,000) times if you are lucky with randomizer. So the total time is about 10,000 x log(10,000).


  • 0
    Z

    If you have the patience to read the code of to look into QuickSort, you will figure out.
    I didn't traverse the whole array in each iteration. I didn't even sort. All that I did was to recursively doing partition over the smaller interval that the target number is likely to appear.
    In the average case, I would get n+n/2+n/4+n/8+... And that converges to 2n.


  • 0
    A

    @zhangc Right. I overlooked. On average, you might get O(2n).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.