int majorityNumber(vector<int> nums) {
sort(nums.begin(),nums.end());
return nums[(nums.size()/2)];
}
};
Just write it for fun as this could be ended using only one line if you use javascript. The complexity is not so good though.
/**
* Memo: Sort the array first, then the majority element will be located at n/2.
* Complex: O(nlogn)
* Runtime: 148ms
* Tests: 40 test cases passed
* Rank: A
* Updated: 2015-06-12
*/
var majorityElement = function(num) {
return num.sort()[num.length>>1];
};
I think the sort() will take NlogN time on average.
In interview, i think this solution is NOT good enough...
If the array is sorted, then the majority number must be equal to the (N/2)th number. We can use quick select to find kth largest number, where k=N/2, N is length of the array. It took O(N) time on average.