链接
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
提示：
- 0 <= nums.length <=
-
<= nums[i] <=
- nums 是一个非递减数组
-
代码框架
class Solution {
public int search(int[] nums, int target) {
}
}
题目解析
辅助思考图形：
[[剑指 Offer 53 - I. 在排序数组中查找数字 I.drawio]]
解答思路1：
暴力解法，从数组头部开始循环，
比较目标数据，计算目标的出现次数，
如果数组的数据大于目标数据，则结束循环。
解答思路2：
使用二分查找法，
递归查找数组，
首先根据low和high的值二分为mid，
和target的比较确定范围，
如果找到了目标，则则计数器加1，
且在mid的前后查找和target相同的元素。
解答思路3：
使用二分查找法，
while循环查找数组，
如果找到目标，
则在附近查找重复的元素。
解答思路4：
使用二分查找法，
while循环查找数组，
第一遍循环，
找出第一个等于target的下标tFirst,
第二遍循环，
找出最后一个等于target的下标tLast;
target的数量就是tLast-tFirst+1。
测试用例
package edu.yuwen.sowrd.num53_I.solution;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import edu.yuwen.sowrd.num53_I.sol4.Solution;
/**
* 输入: nums = [5,7,7,8,8,10], target = 8
* 输出: 2
*/
public class SolutionTest {
@Test
public void testCase1() {
Solution solution = new Solution();
int[] nums = { 5, 7, 7, 8, 8, 10 };
int target = 8;
int count = solution.search(nums, target);
Assertions.assertEquals(2, count);
}
/**
* 输入: nums = [5,7,7,8,8,10], target = 6
* 输出: 0
*/
@Test
public void testCase2() {
Solution solution = new Solution();
int[] nums = { 5, 7, 7, 8, 8, 10 };
int target = 6;
int count = solution.search(nums, target);
Assertions.assertEquals(0, count);
}
/**
* 输入: nums = [1,4], target = 4
* 输出: 1
*/
@Test
public void testCase3() {
Solution solution = new Solution();
int[] nums = { 1, 4 };
int target = 4;
int count = solution.search(nums, target);
Assertions.assertEquals(1, count);
}
/**
* 输入: nums = [1,2,3,3,3,3,4,5,9], target = 3
* 输出: 4
*/
@Test
public void testCase4() {
Solution solution = new Solution();
int[] nums = { 1, 2, 3, 3, 3, 3, 4, 5, 9 };
int target = 3;
int count = solution.search(nums, target);
Assertions.assertEquals(4, count);
}
}
解答1
package edu.yuwen.sowrd.num53_I.sol1;
public class Solution {
public int search(int[] nums, int target) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
int cur = nums[i];
if (cur == target) {
count++;
}
if (cur > target) {
break;
}
}
return count;
}
}
解答2
package edu.yuwen.sowrd.num53_I.sol2;
public class Solution {
int count = 0;
int target;
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
this.target = target;
int low = 0;
int high = nums.length - 1;
binarySearchRecurve(nums, low, high);
return count;
}
private void binarySearchRecurve(int[] nums, int low, int high) {
// 结束二分查找
if (low > high) {
return;
}
int mid = (low + high) / 2;
// 找到目标后，查找附近和目标相等的元素
if (target == nums[mid]) {
count++;
searchNearBy(nums, mid);
// 结束查找
return;
}
// 目标小于中间值，则查找左半边部分
if (target < nums[mid]) {
high = mid - 1;
}
// 目标大于中间值，则查找右半边部分
if (target > nums[mid]) {
low = mid + 1;
}
binarySearchRecurve(nums, low, high);
}
/**
* 在指定索引的前后两边查找target
*/
private void searchNearBy(int[] nums, int mid) {
// 先搜索左边
int left = mid - 1;
while (left >= 0) {
if (target == nums[left]) {
count++;
left--;
continue;
}
// target不相等了，则停止搜索
break;
}
// 再搜索右边
int right = mid + 1;
while (right < nums.length) {
if (target == nums[right]) {
count++;
right++;
continue;
}
// target不相等了，则停止搜索
break;
}
}
}
解答3
package edu.yuwen.sowrd.num53_I.sol3;
public class Solution {
int count = 0;
int target;
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
this.target = target;
int low = 0;
int high = nums.length - 1;
binarySearchLoop(nums, low, high);
return count;
}
private void binarySearchLoop(int[] nums, int low, int high) {
while (low <= high) {
int mid = (low + high) / 2;
// 找到目标target，则统计前后所有的target的数量
if (target == nums[mid]) {
count++;
searchNearBy(nums, mid);
return;
}
// 目标小于中间值，则查找左半边部分
if (target < nums[mid]) {
high = mid - 1;
}
// 目标大于中间值，则查找右半边部分
if (target > nums[mid]) {
low = low + 1;
}
}
}
/**
* 查找index前后和target相同的元素
*/
private void searchNearBy(int[] nums, int index) {
int left = index - 1;
while (left >= 0) {
// 不相等就停止查找
if (target != nums[left]) {
break;
}
count++;
left--;
}
int right = index + 1;
while (right < nums.length) {
// 不相等就停止查找
if (target != nums[right]) {
break;
}
count++;
right++;
}
}
}
解答4 推荐
package edu.yuwen.sowrd.num53_I.sol4;
public class Solution {
int target;
int tFirst = -1;
int tLast = -1;
public int search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
this.target = target;
int low = 0;
int high = nums.length - 1;
binarySeachFirst(nums, low, high);
binarySeachLast(nums, low, high);
if (tFirst != -1 && tLast != -1) {
return tLast - tFirst + 1;
}
return 0;
}
/**
* 二分搜索第一个等于target的下标
*/
private void binarySeachFirst(int[] nums, int low, int high) {
while (low <= high) {
int mid = (low + high) / 2;
if (target == nums[mid]) {
// 确保找到最左边
if (mid == 0 || nums[mid - 1] != target) {
tFirst = mid;
break;
}
// 否则进一步查找左边的部分
else {
high = mid - 1;
}
}
// 如果目标小于中间值，则查找左半边部分
if (target < nums[mid]) {
high = mid - 1;
}
// 如果目标值大于中间值，则查找右半边部分
if (target > nums[mid]) {
low = mid + 1;
}
}
}
/**
* 二分搜索最后一个等于target的下标
*/
private void binarySeachLast(int[] nums, int low, int high) {
while (low <= high) {
int mid = (low + high) / 2;
// 该处逻辑是和binarySeachFirst的唯一区别
if (target == nums[mid]) {
// 确保找到最右边
if (mid == nums.length - 1 || nums[mid + 1] != target) {
tLast = mid;
break;
}
// 否则进一步查找右边的部分
else {
low = mid + 1;
}
}
// 如果目标小于中间值，则查找左半边部分
if (target < nums[mid]) {
high = mid - 1;
}
// 如果目标值大于中间值，则查找右半边部分
if (target > nums[mid]) {
low = mid + 1;
}
}
}
}
网友评论