在排序数组中查找数字
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [
5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [
5,7,7,8,8,10], target = 6
输出: 0
我的思路：二分查找到target，再分别向前向后找等于target的值
public int search(int[] nums, int target) {
int low=0;
int high=nums.length-1;
int count=0;
while(low<=high){
int mid=(low+high)/2;
if(nums[mid]==target){
return getCount(nums,mid,target);
} else if(nums[mid]<target){
low=mid+1;
} else{
high=mid-1;
}
}
return 0;
}
public int getCount(int[] nums,int mid,int target){
int i=mid-1;
int count=1;
while(i>=0&&nums[i]==target){
count++;
i--;
}
i=mid+1;
while(i<nums.length&&nums[i]==target){
count++;
i++;
}
return count;
}
方法二：两次二分确定左右边界
public int search(int[] nums, int target) {
int low=0;
int high=nums.length-1;
//确定右边界（不含等于)
while (low<=high){
int mid=(low+high)/2;
if(nums[mid]<=target){
low=mid+1;
} else {
high=mid-1;
}
}
int right=low;//可以理解为遇到小于等于情况都会往后移动，最终会是最后一个等于target的下一个位置
low=0;
high=nums.length-1;
//确定左边界（含等于)
while (low<=high){
int mid=(low+high)/2;
if(nums[mid]<target){
low=mid+1;//可以理解为遇到小于情况都会往后移动，最终会是第一个等于target的位置
} else {
high=mid-1;
}
}
return right-low;
}
改进：寻找左右边界可以看做是找插入点
public int search(int[] nums, int target) {
// 如果不存在的话，low会是比target最小的一个元素的后面一个位置
// mid 最终是会靠近target可能存在的位置
// 考虑low = high时，如果nums[mid] < target, low = mid + 1，返回的是low，即小于的元素的后一位
// 如果nums[mid] < target, high = mid - 1，返回的是low，即nums[mid], 它比target稍大
return insertPos(nums,target)-insertPos(nums,target-1);
}
//找到应该插入的位置，可以看做是target的右边界(不包含target)
public int insertPos(int[] nums,int target){
int low=0;
int high=nums.length-1;
while (low<=high){
int mid=(low+high)/2;
// 当nums[mid] = target时，且是最右边的元素，low会刚好移动到mid的后面一位，那么之后的循环nums[mid]都会大于target，high会向左移直到移动到low的左边，返回low相当于返回的最右边值的后一位
if(nums[mid]<=target){
low=mid+1;
} else {
high=mid-1;
}
}
return low; //或者right + 1
}
// 或者 左闭右开
private int lowerBound(int[] scores, int target) {
int left = 0, right = scores.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (scores[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left; // 或者right
}
在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [
5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [
5,7,7,8,8,10], target = 6
输出: [-1,-1]
二分查找，找到元素后再分别向前、向后查找
public int[] searchRange(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
int[] ans = new int[2];
Arrays.fill(ans, -1);
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
//向前找第一次出现的位置
int i;
int j;
for (i = mid - 1; i >= 0; i--) {
if (nums[i] != target) {
break;
}
}
//向后找最后出现的位置
for (j = mid + 1; j < nums.length; j++) {
if (nums[j] != target) {
break;
}
}
ans[0] = i + 1;
ans[1] = j - 1;
break;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
确定左右边界
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
res[0] = searchLeft(nums, target);
if (res[0] == -1) {
return new int[]{-1, -1};
}
res[1] = searchRight(nums, target);
return res;
}
public int searchLeft(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] < target) {
low = mid + 1;
} else {
// nums[mid] == target时，考虑mid已经是最左边的元素，high向左移动，nums[high]会比target小，之后再循环时nums[mid] < target,low会向右亿，最终会达到之前的最左边的目标元素的位置
high = mid - 1;
}
}
// 因为low不会等于-1，判断一下跳出循环时nums[low]是否为目标值
if (low < nums.length && nums[low] == target) {
return low;
}
return -1;
}
public int searchRight(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] <= target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return high;
}
0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例 1:
输入: [0,1,3]
输出: 2
示例 2:
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
限制：
1 <= 数组长度 <= 10000
我的思路：依次比较，时间复杂度O(n)
public int missingNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] != i) {
return i;
}
}
return nums.length;
}
二分查找
既然是有序数组，考虑使用二分
每次二分，一部分不存在缺失数字，而另一部分存在
public int missingNumber(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (mid == nums[mid]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
有序数组中出现次数超过25%的元素
给你一个非递减的 有序整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
请你找到并返回这个整数
示例：
输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6
方法一：统计元素个数
当找到一个元素出现次数大于25%时返回
方法二：滑动窗口
因为有序，如果某个位置后面1/4长度的元素和当前元素相等，说明它就是目标元素
public int findSpecialInteger(int[] arr) {
int windowSize = arr.length / 4;
for (int i = 0; i + windowSize < arr.length; i++) {
if (arr[i] == arr[i + windowSize]) {
return arr[i];
}
}
return -1;
}
方法三：二分查找
根据题目要求，满足条件的整数 x 至少在数组 arr 中出现了 span = arr.length / 4 次，那么我们可以断定：数组 arr 中的元素 arr[0], arr[span], arr[span * 2], ... 一定包含 x
我们可以使用反证法证明上述的结论。假设 arr[0], arr[span], arr[span * 2], ... 均不为 x，由于数组 arr 已经有序，那么 x 只会连续地出现在 arr[0], arr[span], arr[span * 2], ... 中某两个相邻元素的间隔中，因此其出现的次数最多为 span - 1 次，这与它至少出现 span 次相矛盾
有了上述的结论，我们就可以依次枚举 arr[0], arr[span], arr[span * 2], ... 中的元素，并将每个元素在数组 arr 上进行二分查找，得到其在 arr 中出现的位置区间。如果该区间的长度至少为 span，那么我们就得到了答案
public int findSpecialInteger(int[] arr) {
int span = arr.length / 4;
for (int i = 0; i < arr.length; i += span) {
int left = leftBound(arr, arr[i]);
int right = rightBound(arr, arr[i]);
if (right - left >= span) {
return arr[i];
}
}
return -1;
}
public int leftBound(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] >= target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return low;
}
public int rightBound(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return high;
}
