def Moore_voting(list_): curIdx = 0 count = 1 for i in range(1, len(list_)): if list_[i] == list_[curIdx]: count += 1 else: count -= 1 if count == 0: curIdx = i count = 1 return list_[curIdx]
// // Created by oujie on 2019-08-05. // #include <iostream> #include <vector> #include <unordered_map> using namespace std; class Solution{ public: int findMoreHalf(vector<int> array){ unordered_map<int,int> mymap; for(auto num:array){ auto iter=mymap.find(num); if(iter==mymap.end()){ mymap.insert(pair<int,int>(num,1)); }else{ (iter->second)+=1; if((iter->second)>(array.size()/2.)) return iter->first; } } } }; int main(){ vector<int> nums={1,1,1,2,2,2,2,2,3}; Solution s; cout<<s.findMoreHalf(nums); return 0; }
#include<iostream> using namespace std; class Solution{ public: int overhalf(vector<int>nums){ int count=1; int cur=nums[0]; for(int i=1;i<n;i++){ if(count==0){ cur=nums[i]; count=1; continue; } if(nums[i]==cur){count++;} else{ count--; } } return cur; } }
import java.util.ArrayList; import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Ans { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] arr = new int[n]; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < arr.length; i++) { if(map.containsKey(arr[i])){ map.put(arr[i], map.get(arr[i]+1)); }else{ map.put(arr[i], 1); } } ArrayList<Integer> list = new ArrayList<>(map.keySet()); for (int i = 0; i < list.size(); i++) { if(map.get(list.get(i))>n/2){ System.out.println(list.get(i)); } } } }