Majority Element

• Approach #6 fails for the following case where it returns 7 instead of -7
[]int{-7, 2, 3, 4, 5, 6, -7, -7, 7, 7, 7, -7}

• In fact, count must be set to 1 as follows
if (count == 0) {
candidate = num;
count = 1;
}

• @swatisaoji1 That array does not have a majority element, so it is not a valid input for this problem.

• Another easy solution: K being a majority item means that every bit value of K is majority. We can then reconstruct K from the majority bit values.

• [7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 6, 6, 6, 6]
apporach #6 result is 6 not expected 7，so the approach is wrong!

• @zpng The problem states that only arrays with a majority element will be passed as input. Your array does not have a majority element, so it is not valid input. For the version of the problem that works with arrays that may or may not have a majority element, you need to make a final linear pass over the array, verifying that the `candidate` is indeed a majority element.

• ``````public int majorityElement(int[] nums) {
``````

HashMap<Integer, Integer> ht = new HashMap<>();
int value = 0;
for(int i : nums){
if(ht.containsKey(i)){
ht.put(i, 1+ht.get(i));
if(ht.get(i)>nums.length/2){
value=i;
}
}
else{
ht.put(i, 1);
}
}
return nums.length==1 ? nums[0] : value;
}

• This post is deleted!

• class Solution {
public int majorityElement(int[] nums) {
if (nums.length == 0)
return -1;

``````    int majorElem = nums[0], count = 1;

for (int i=1; i<nums.length; i++) {
if (nums[i] == majorElem) {
count++;
} else {
count --;
}
if (count == 0) {
majorElem = nums[i];
count = 1;
}
}

if (count > nums.length/2)
return majorElem;

count = 0;

for (int i=0; i<nums.length; i++) {
if (nums[i] == majorElem) {
count++;
}

if (count > nums.length/2)
break;
}

return count > nums.length/2 ? majorElem : -1;
}
``````

}

• Python's `sort` takes O(n) space. It's only sort of in-place.

• Boyce-Moore Algorithms is the one which is worth understanding in this.

• Thank you for explaining Boyer-Moore algorithm, that's very interesting. I was curious is it possible to optimize O(n) time solution to use only O(1) space. Turns out it is possible :)

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