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

• ``````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;
}

};``````

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