# # # @param arr int整型一维数组 the array # @return int整型 # class Solution: def findNum(self , arr ): # write code here dic = dict() for i in arr: if i not in dic: dic[i] = 1 else: dic[i] += 1 maxx = max(zip(dic.values(), dic.keys())) if maxx[0] > len(arr) //2: return maxx[1] else: return -1
若题目为一定存在次数超过一半的数字,找出该数字 那么问题为求解序列的中位数,可采取快速排序的思想,寻找中位数 另一种思路,若当前数字与之前相等,那么次数++ 否则次数-- 当次数为0时,换上新的数字 即:不同的一组数字 两两消去,剩下的即可能为超过一半的数字,在遍历一次,验证即可 复杂度: O(N) int findNum(vector<int>& arr) { // write code here int time=1; int result=arr[0]; for(int i=0;i<arr.size();i++) { if(time==0) //前面都已经消去 { result=arr[i]; time=1; } if(arr[i]==result) //相等就累积上 { time++; } else{ //不相等就成对消去 time--; } } int k=0; //最终剩下来的result即为 for(int i=0;i<arr.size();i++) if(arr[i]==result) k++; if(2*k>arr.size()) return result; else return -1; }