169. Majority Element

时间:2022-09-01 16:59:27

题目:

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.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

链接: http://leetcode.com/problems/majority-element/

题解:

找Major Element, more than [n / 2] times。可以使用Boyer-Moore's Majority Voting Algorithms - 设定一个candidate,一个count。在count = 0时设置candidate为当前nums[i],假如candidate == nums[i],count++,否则count--。 可能会有的follow up是,找more than [n / 3] 和 [n / 4] times的major elements, 这时我们要根据[n / theta]中theta的大小来设置一个HashMap<Integer,Integer>来记录Integer以及count。当integer不在map中时,我们把put(integer, 1),否则put(integer, count + 1)。当map.size() > [1/theta]时,遍历map,每个key的count--,当count == 0时,delete这个key。 最后返回map中count > 1/theta的值。 这样的花时间复杂度是O(n),空间复杂度是O(1)。

Time Complexity - O(n), Space Complexity - O(1)。最后其实应该再过一遍数组来检查这个元素是否是majority element

public class Solution {
public int majorityElement(int[] nums) {
if(nums == null || nums.length == 0)
return 0;
int candidate = 0, count = 0; for(int i = 0; i < nums.length; i++) {
if(count == 0)
candidate = nums[i];
if(nums[i] == candidate)
count++;
else
count--;
} return candidate;
}
}

又思考了一下general的case,假如给定一个数组,要求majority elements,这些elements出现 > 数组的theta (比如theta = 0.3, 0.4,0.5)。方法应该是如下:  Time Complexity - O(n), Space Complexity - O(1 / theta)。

1) 建立一个k个数的map, 比如more than [1/2]则 k = 1, more than [1/3]则 k  = 2, more than [1/4]则 k = 3。

2) 当map.size() > k时,对map中每个元素进行count--,移除 = 0元素

3) 对map中剩余元素进行count++

4)最后输出map中count > theta * n的元素。

二刷:

Boyer-Moore选择问题。可以使用一个count一个candidate很容易的找到比n/2大的元素。要注意的是题目给出这样元素存在在数组里,  假如没有这个条件,我们在最后还要再判断一下这个candidate是否count > n / 2.

Java:

Time Complexity - O(n), Space Complexity - O(1)

public class Solution {
public int majorityElement(int[] nums) {
if (nums == null | nums.length == 0) {
return -1;
}
int candidate = 0, count = 0;
for (int i = 0; i < nums.length; i++) {
if (count == 0) {
candidate = nums[i];
count++;
} else {
count = nums[i] == candidate ? count + 1 : count - 1;
}
}
/*
count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == candidate) {
count++;
}
if (count > nums.length() / 2) {
break;
}
}
return count > nums.length() / 2 ? candidate : -1;
*/
return candidate;
}
}

三刷:

Boyer-Moore选择

Java:

public class Solution {
public int majorityElement(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int candidate = 0, count = 0; for (int num : nums) {
if (count == 0) {
candidate = num;
count++;
} else if (num == candidate) {
count++;
} else {
count--;
}
}
for (int num : nums) {
if (candidate == num) {
count++;
}
}
return (count >= nums.length / 2) ? candidate : 0;
}
}

Reference:

http://www.cs.yale.edu/homes/el327/datamining2011aFiles/ASimpleAlgorithmForFindingFrequentElementsInStreamsAndBags.pdf

https://leetcode.com/discuss/43248/boyer-moore-majority-vote-algorithm-and-my-elaboration

http://*.com/questions/24691048/find-all-elements-that-appear-more-than-n-4-times-in-linear-time

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm