My c++ solution, O(n) time, O(1) space averagely, different from previous solutions.


  • -1
    A
    Obviously  my program will stop after O(1) recursions averagely.
    
    
    class Solution {
    public:
        vector<int> majorityElement(vector<int>& nums) {
            int len = nums.size();
            int th = len / 3;
            if(len <= 1)
                return nums;
            if(len == 2)
            {
                if(nums[0] != nums[1])
                    return nums;
                else
                {
                    nums.pop_back();
                    return nums;
                }
            }
            srand(time(NULL));
            int i,j,temp,count = 0;
            for(i = 0; i < len; i++)
            {
                int pos = rand() % len;
                temp = nums[i];
                nums[i] = nums[pos];
                nums[pos] = temp;
            }
            return mE(nums,0,len, len);
    
            
        }
        vector<int> mE(vector<int>& nums, int m, int n, int len)
        {
            vector<int> result;
            int th = len / 3, count = 0, temp, i, j;
            if(n - m < th)
                return result;
            for(i = m + 1,j = n - 1; i <=j;)
            {
                if(nums[i] < nums[m])
                {
                    i++;
                    continue;
                }
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                if(temp == nums[m])
                {
                    nums[j] = nums[n - 1];
                    nums[n - 1] = temp;
                    count++;
                    n--;
                }
                j--;
            }
            temp = nums[m];
            nums[m] = nums[i - 1];
            nums[i - 1] = temp;
        if(count + 1 > th)
            result.push_back(nums[i - 1]);
        vector<int> leftResult = mE(nums,m, i - 1,len);
        vector<int> rightResult = mE(nums,i,n,len);
        for(i = leftResult.size() - 1; i >= 0; i--)
        {
            result.push_back(leftResult[i]);
        }
        for(i = rightResult.size() - 1; i >= 0; i--)
        {
            result.push_back(rightResult[i]);
        }
        return result;
        }
        
    };

Log in to reply
 

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