LEET code -- Majority Element

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.


起手式 先sort
但是事實上可以不用for去找
因為他說一定會超過一半的數量
所以直接中位數就好

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

int cmp(const void * s1, const void *s2){ int a=*(int*)s1; int b=*(int*)s2; if(a>b)return 1; if(a==b)return 0; else return -1; } int majorityElement(int* nums, int numsSize) { if(numsSize==1)return nums[0]; qsort(nums,numsSize,sizeof(int),cmp); int max=0,ans=0; for(int i=0;i<numsSize;){ if(nums[i]!=nums[i+1])i++; else { int localmax=0; for(int j=i;j<numsSize;j++){ if(nums[i]==nums[j])localmax++; else{ printf("%d",localmax); break; } i=j; } if(localmax > max){ max = localmax; ans = nums[i]; } } } return ans; }

1 2 3 4 5 6 7 8 9 10 11 12

int cmp(const void * s1, const void *s2){ int a=*(int*)s1; int b=*(int*)s2; if(a>b)return 1; if(a==b)return 0; else return -1; } int majorityElement(int* nums, int numsSize) { qsort(nums,numsSize,sizeof(int),cmp); return nums[numsSize/2]; }

-------------
特殊解法

Boyer–Moore majority vote algorithm

https://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html

只能用在 重複數字超過 總數/2 以上的時機點
演算法:
利用一個counter來計算次數，跟candidate代表可能答案
一開始先把counter=1,candidate=第一個數字
如果下一個遇到依樣的counter++

如果不一樣就counter--
如果counter==0 就把candidate更新，再把counter=1

因為重複出現的超過總數/2  所以這演算法可以成功

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

int majorityElement(int* nums, int numsSize) { int candidate = nums[0], counter=1; for(int i =1;i< numsSize;i++){ if(nums[i] == candidate){ counter++; }else{ if(counter==0){ candidate=nums[i]; counter=0; }else{ counter--; } } } return candidate; }