http://shibaili.blogspot.com/2015/06/google-interview-questions.html
4.(1)一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return
true。就是说{2，2，3，4} return true
{1，1，2，3，4，5，6，7} return false。
（2）优化第一部分用O（log2(N)) 时间复杂度
如果存在超过 1/4 的数，则次数必定会覆盖length / 4, length / 2, length *（3 / 4）这3点中的至少一点，所以只要对这3点上的数做二分搜索，就能找到其长度，然后与 1 / 4的长度对比。复杂度为 O(lgN)
https://gist.github.com/gcrfelix/bec1a9d229dcf41248bc
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。
4.(1)一个sorted array，如果其中有一个数重复超过array里面总数的1/4 return
true。就是说{2，2，3，4} return true
{1，1，2，3，4，5，6，7} return false。
（2）优化第一部分用O（log2(N)) 时间复杂度
如果存在超过 1/4 的数，则次数必定会覆盖length / 4, length / 2, length *（3 / 4）这3点中的至少一点，所以只要对这3点上的数做二分搜索，就能找到其长度，然后与 1 / 4的长度对比。复杂度为 O(lgN)
int findFirst(vector<int> &nums, int elem) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == elem) { if (mid - 1 >= 0 && nums[mid - 1] != nums[mid]) { return mid; } right = mid - 1; }else if (nums[mid] > elem) { right = mid - 1; }else { left = mid + 1; } } return 0;}int findLast(vector<int> &nums, int elem) { int left = 0, right = nums.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] == elem) { if (mid + 1 < nums.size() && nums[mid + 1] != nums[mid]) { return mid; } left = mid + 1; }else if (nums[mid] > elem) { right = mid - 1; }else { left = mid + 1; } } return 0;}bool helper(vector<int> &nums, int index) { int last = findLast(nums,nums[index]); int first = findFirst(nums,nums[index]); if (last - first + 1 > nums.size() / 4) { return true; } return false;}bool longerThanAQuarter(vector<int> &nums) { int length = nums.size(); return helper(nums,length / 4) || helper(nums,length / 2) || helper(nums,length - 1 -length / 4);}https://gist.github.com/gcrfelix/bec1a9d229dcf41248bc
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。
