Why does my code of median selection work?


  • 0
    J

    Index mapping and 3-way partition is OK for me. And I know that average linear time median selection can be achieved by a quick-sort like approach. In my following algorithm, the smaller part is on the left side while the larger part is on the right side, median has index (n/2).
    I have two versions of AC codes, the first one has an iteration counter "nIt". When I set the upper bound of this counter to be 5, the code works fine, and can achieve 82ms in C++ (together with other functions). If I remove this counter, the code still works, but then it may take as much as 400ms in C++ (together with the same other functions).
    My hypothesis is that the test case lacks some counter case with large array, otherwise, the "nIt" one can not get accepted. Can you please confirm my conjecture? Thanks! The first function is the "nIt" one, while the second function is the counter-free and slower one.

    
      int returnMedian(vector<int> & nums)
      {
        int n=nums.size(), l=0, r=nums.size()-1, L=0, R=nums.size()-1, pivot, targetIndex=0;
        targetIndex = n/2;
        int nIt = 0;
        // the outer loop specifies boundary while the inner loop swaps the elements
        while (L<R)
        {
          pivot = nums[L];
          l = L; r = R;
          while (l<r)
          {
            while ((l<r)&&(nums[r]>pivot))
              r--;
            if (l<r)
              nums[l++] = nums[r];
            while ((l<r)&&(nums[l]<=pivot))
              l++;
            if (l<r)
              nums[r--] = nums[l];
          }
          nums[l] = pivot;
          if (l>targetIndex)  // should use the left half
            R = l-1;
          else if (l==targetIndex)
            return nums[targetIndex];
          else  // should use the right half
            L = l+1;
          nIt++;
          if (nIt==5)
            break;
        }
        return nums[targetIndex];
      }  
    
    
      int returnMedian(vector<int> & nums)
      {
        int n=nums.size(), l=0, r=nums.size()-1, L=0, R=nums.size()-1, pivot, targetIndex=0;
        targetIndex = n/2;
        while (L<R)
        {
          pivot = nums[L];
          l = L; r = R;
          while (l<r)
          {
            while ((l<r)&&(nums[r]>pivot))
              r--;
            if (l<r)
              nums[l++] = nums[r];
            while ((l<r)&&(nums[l]<=pivot))
              l++;
            if (l<r)
              nums[r--] = nums[l];
          }
          nums[l] = pivot;
          if (l>targetIndex)  // should use the left half
            R = l-1;
          else if (l==targetIndex)
            return nums[targetIndex];
          else  // should use the right half
            L = l+1;
        }
        return nums[targetIndex];
      }  
    

Log in to reply
 

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