leetcode 229. Majority Element II (O(1)空间找出现次数大于n/3的元素)

Given an integer array of size n, find all elements that appear more than n/3 times. The algorithm should run in linear time and in O(1) space.

题意:给你n个数,要求找出出现此处大于n/3的。。。

思路:之前做过一个找出n个数出现此处大于n/2的题目,思想是“非吾族类,其心必异”。。

这道题类似。。。容易知道题目要求的数最多有2个,最少有0个。。。

由于最多两个“族类”,在更新的时候,要判断是不是友军的人…毕竟朋友妻不可欺嘛(什么鬼

最后记得扫一遍,check一下,检查出现此处是否满足题意。

 

 

说点什么

您将是第一位评论人!

提醒
wpDiscuz