Special Array With X Elements Greater Than or Equal X
求一个数字x, 数组中的数字大于等于x的数字个数正好是x. 如果有x, 返回x, 否则返回 -1.
这个题首先看肯定是O(n^2)能解决的, 就是暴力破解. 然后这题一看x是对大小有考量, 肯定用binary search能优化, 用二叉肯定要先找边界, 所以看题知道边界是[0, n]. 然后再看用哪种二叉搜索, 这题因为答案唯一(题中给了, 不给的话自己prove很难, 我估计着狗家这题肯定是没告诉你答案必然唯一的, 如果想不到答案必然唯一, 这题很难在短时间写出来.), 剩下的就直接就写出来了..
class Solution {
public int specialArray(int[] nums) {
Arrays.sort(nums);
int start = 0;
int end = nums.length;
while(start <= end) {
int mid = start + (end - start) / 2;
int c = count(nums, mid);
if(c == mid){
return mid;
} else if(c > mid) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return -1;
}
private int count(int[] nums, int i) {
int c = 0;
for(int n : nums) {
if(n >= i)
c++;
}
return c;
}
}