(LeetCode 面试经典 150 题) 169. 多数元素（哈希表 || 二分查找）

方法一：二分法，最坏的时间复杂度0(nlogn)，但平均0(n)即可。空间复杂度为0(1)。

C++版本：

int n=nums.size();int l=0,r=n-1;while(l<r){int mid=(l+r)/2;int ans=0;for(auto x:nums){if(x==nums[mid]) ans++;}if(ans>n/2) break;else l=mid+1;}return nums[(l+r)/2];

JAVA版本：

class Solution {public int majorityElement(int[] nums) {int n=nums.length;int l=0,r=n-1;while(l<r){int mid=(l+r)/2;int ans=0;for(var x:nums){if(x==nums[mid]) ans++;}if(ans>n/2) break;else l=mid+1;}return nums[(l+r)/2];}
}

Go版本：

func majorityElement(nums []int) int {n:=len(nums)l,r:=0,n-1for l<r {mid:=(l+r)/2ans:=0for _,x:=range nums {if nums[mid]==x {ans++}}if ans>n/2 {break}else{l=mid+1}}return nums[(l+r)/2]
}

方法二：哈希表，时间复杂度0(n)，空间复杂度0(n)。

C++版本：

class Solution {
public:int majorityElement(vector<int>& nums) {unordered_map<int,int> mp;int n=nums.size();int res=0;for(auto x:nums){mp[x]++;if(mp[x]>n/2){res=x;break;}}return res;}
};

JAVA版本：

class Solution {public int majorityElement(int[] nums) {Map<Integer,Integer> mp = new HashMap<>();int n=nums.length;int res=0;for(var x:nums){mp.put(x,mp.getOrDefault(x,0)+1);if(mp.get(x)>n/2){res=x;break;}}return res;}
}

Go版本：

func majorityElement(nums []int) int {n:=len(nums)mp:=make(map[int]int)res:=0for _,x:=range nums {mp[x]++if mp[x]>n/2 {res=xbreak}}return res
}