Leetcode[169, 229] Majority Element
15 Nov 2015###Task1 Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array. ###Python
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = nums[0]
count = 1
for num in nums[1:]:
if num == res:
count += 1
elif count > 0 and num != res:
count -= 1
elif count == 0:
res = num
count = 1
return res
###Java
public class Solution {
public int majorityElement(int[] nums) {
int res = 0;
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (count == 0) {
res = nums[i];
count++;
} else if (res == nums[i]) {
count++;
} else if (res != nums[i]) {
count--;
}
}
return res;
}
}
###Task2 Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
Hint:
How many majority elements could it possibly have? Do you have a better hint? Suggest it!
###Python
class Solution(object):
def majorityElement(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
if not nums or len(nums) < 2:
return nums
count1 = 0
count2 = 0
res1 = 0
res2 = 0
for num in nums:
if num == res1:
count1 += 1
elif num == res2:
count2 += 1
elif count1 == 0:
res1 = num
count1 = 1
elif count2 == 0:
res2 = num
count2 = 1
else:
count1 -= 1
count2 -= 1
count1 = 0
count2 = 0
for num in nums:
if num == res1:
count1 += 1
elif num == res2:
count2 += 1
ret = []
if count1 > len(nums) / 3:
ret.append(res1)
if count2 > len(nums) / 3:
ret.append(res2)
return ret
###Java
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return res;
}
int ele1 = 0;
int count1 = 0;
int ele2 = 0;
int count2 = 0;
for (int i = 0; i < nums.length; i++) {
if (ele1 == nums[i]) {
count1++;
} else if (ele2 == nums[i]) {
count2++;
} else if (count1 == 0) {
ele1 = nums[i];
count1++;
} else if (count2 == 0) {
ele2 = nums[i];
count2++;
} else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int i = 0; i < nums.length; i++) {
if (ele1 == nums[i]) {
count1++;
} else if (ele2 == nums[i]) {
count2++;
}
}
if (count1 > nums.length / 3) {
res.add(ele1);
}
if (count2 > nums.length / 3) {
res.add(ele2);
}
return res;
}
}
###Points
- There could be at most two elements have ratio larger than 1 / 3
- Res could be set to 0 before iteration. why ? count == 0 so even if the first element is 0, it is still correct.