剑指 Offer 53 - I. 在排序数组中查找数字 I
直达链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
解题思路:
1、暴力法:
(1) 因为是已经排序,先用target比较数组的第一个元素和最后一个元素判断查找的元素是否存在,如果不存在直接返回0
(2) 定义一个标记数count,遍历整个数组,当数组中的元素和target相同,count+1
class Solution { public int search(int[] nums, int target) { int count=0; if(nums.length==0) return 0; if(target<nums[0]||target>nums[nums.length-1]) return 0; for(int i=0;i<nums.length;i++){ if(nums[i]==target) count++; } return count; } }
时间、空间复杂度:
2、二分查找:
(1)两次二分查找
由于数组已经排序,因此整个数组是单调递增的,可以利用二分法来加速查找的过程。首先找到第一个出现target的位置left,其次找到第一个比target大的数的位置right,right-left+1就得到出现次数。 关键:如何找到第一个target出现的位置
二分查找中,寻找 leftIdx 即为在数组中寻找第一个大于等于target 的下标,寻找 rightIdx 即为在数组中寻找第一个大于 target 的下标,然后将下标减一。两者的判断条件不同,为了代码的复用,我们定义 binarySearch(nums, target, lower) 表示在nums 数组中二分查找target 的位置,如果 ower 为true,则查找第一个大于等于arget 的下标,否则查找第一个大于target 的下标。因为target 可能不存在数组中,因此我们需要重新校验我们得到的两个下标 leftIdx 和 rightIdx,看是否符合条件,如果符合条件就返回rightIdx-leftIdx+1,不符合就返回 0。
参考链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-wl6kr/
class Solution { public int search(int[] nums, int target) { int leftIdx = binarySearch(nums, target, true); int rightIdx = binarySearch(nums, target, false) - 1; if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) { return rightIdx - leftIdx + 1; } return 0; } public int binarySearch(int[] nums, int target, boolean lower) { int left = 0, right = nums.length - 1, ans = nums.length; while (left <= right) { int mid = (left + right) / 2; if (nums[mid] > target || (lower && nums[mid] >= target)) { right = mid - 1; ans = mid; } else { left = mid + 1; } } return ans; } }
时间、空间复杂度:
(2)二分单边+线性扫描
二分查找,找到目标值 target 「首次」出现或者「最后」出现的下标,然后「往后」或者「往前」进行数量统计。
参考链接:
class Solution { public int search(int[] nums, int t) { int n = nums.length; int l = 0, r = n - 1; while (l < r) { //二分查找最后出现位置 int mid = (l + r + 1)/2; if (nums[mid] <= t) l = mid; else r = mid - 1; } int ans = 0;//向前遍历 while (r >= 0 && nums[r] == t && r-->= 0) ans++; return ans; } }
时间、空间复杂度: