Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.
Follow-up: Could you solve the problem in linear time and in O(1) space?
Example 1:
Input: nums = [3,2,3] Output: [3] Example 2:
Input: nums = [1] Output: [1] Example 3:
Input: nums = [1,2] Output: [1,2]
Constraints:
1 <= nums.length <= 5 * 104 -109 <= nums[i] <= 109
public class Solution {
public IList<int> MajorityElement(int[] nums) {
var result = new List<int>();
if(nums.Length == 0 ){
return result;
}
int number1 = nums[0];
int number2 = nums[0];
int count1 = 0;
int count2 = 0;
int len = nums.Length;
for(int i=0;i<len;i++){
if(nums[i]==number1){
count1++;
}
else if(nums[i]==number2){
count2++;
}
else if(count1==0){
number1 = nums[i];
count1 = 1;
}
else if(count2==0){
number2 = nums[i];
count2 = 1;
}
else{
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for(int i=0;i<len;i++){
if(nums[i]==number1){
count1++;
}
else if(nums[i]==number2){
count2++;
}
}
if(count1>len/3){
result.Add(number1);
}
if(count2>len/3){
result.Add(number2);
}
return result;
}
}Time Complexity: O(n)
Space Complexity: O(1)
