Last active
November 3, 2015 19:21
-
-
Save gcrfelix/bec1a9d229dcf41248bc to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
popular number: 返回一个已经排序好的数组中超过四分之一的数 | |
解法一:找到3个四分点,分别应用search for range,O(logn) | |
因为数组是排序的,所以如果有答案一定是在nums[n/4], nums[2n/4], nums[3n/4]中的一个, | |
所以用Binary Search的方法找到这三个的开始和结尾,获得长度,取最大的那个 | |
解法二:这个是O(N)时间,O(1)空间的做法 | |
每次扔掉四个不同的element,直到最后剩下的就是popular. | |
因为popular的数量超过1/4,所以无论怎么扔,popular都不会被扔完。 | |
开一个大小为3的hashmap,记录目前为止出现频率最高的三个元素->他们的频率。 | |
当遇到新的元素x时: | |
1.如果x在列表里,对应frequence+1 | |
2.如果x不在列表里,检查列表里当前是否有frequence == 0的元素y,用x->0取代y->0。 | |
3.如果x不在列表里,且列表里所有元素的frequence都不为0,那么列表里所有元素的frequence-1。 | |
最后检查列表里剩下的三个元素,是否满足总count>1/4。 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment