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很难, 我估计着狗家这题肯定是没告诉你答案必然唯一的, 如果想不到答案必然唯一, 这题很难在短时间写出来.), 剩下的就直接就写出来了..
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
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; } } |