# 转发: 狗家新鮮店面

1.
Given an array “log” with N entries (N in the order of billions) and M type of numbers in the array. Define a function isMoreThanHalf(startIdx, endIdx, logType). Determine if the “logType” appears more than half of the subarray starts from “startIdx” and ends in “endIdx”.
For example,
log = [6, 6, 6, 7, 3, 8]
isMoreThanHalf(0, 3, 6) -> True
isMoreThanHalf(1, 4, 6) -> False
isMoreThanHalf(2, 5, 7) -> False

Note: startIdx and the endIdx is the closed interval.
startIdx could be the same as endIdx.

You are now able to use a preprocess function one time. How would you define the function?
def preprocess():

1. How would you utilize your preprocess function to improve 1. ?

Binary search可以用 因为index是递增的

1: 2
2: 3 4 5
3: 6
4: 1
6: 0 7
query (2, 4, 2)
2: [3 4 5]
binary search 找 2: 找到index 0
binary search 找 4: 找到index 1
len = 1 - 0 + 1 = 2
2 > 3 / 2 = 1

m * n
m log类型数目
n log总条数

[Java] 纯文本查看 复制代码public static void main(String[] args){
int[] nums = {7,5,7,7};
MoreThanHalf m = new MoreThanHalf(nums);
System.out.println(m.isMoreThanHalf(0, 3, 6));
System.out.println(m.isMoreThanHalf(1, 3, 7));
System.out.println(m.isMoreThanHalf(2, 5, 7));
System.out.println(m.isMoreThanHalf(4, 10, 4));
}

``````static class MoreThanHalf{
Map<Integer, List<Integer>> myMap;
int numsLength;
MoreThanHalf(int[] nums){
numsLength = nums.length;
myMap = new HashMap<>();
for(int i=0; i<numsLength; i++){
if(!myMap.containsKey(nums[i]))
myMap.put(nums[i], new ArrayList<>());
}
}

boolean isMoreThanHalf(int start, int end, int log){
if(start < 0 || end >= numsLength || !myMap.containsKey(log))
return false;
int length = end - start + 1;
int low = binarySearch(start, myMap.get(log), true);
int upper = binarySearch(end, myMap.get(log), false);
return (upper - low + 1) * 2 > length;
}

private int binarySearch(int target, List<Integer> nums, boolean findLowerBound){
int low = 0, high = nums.size() - 1;
while(low + 1 < high){
int mid = low + ((high - low) >> 1);
if(nums.get(mid) > target)
high = mid;
else if(nums.get(mid) < target)
low = mid;
else
return nums.get(mid);
}
if(findLowerBound){
if(nums.get(low) >= target)
return nums.get(low);
return nums.get(high);
}

// find upperbound
if(nums.get(high) <= target)
return nums.get(high);
return nums.get(low);

}
}``````

log里的数不是随机的嘛，binary search的原理是什么