提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

在排序数组中查找数字I（剑指offer 53-I）

数组 排序
2023-03-14 22:48:28 时间

一、题目描述


统计一个数字在排序数组中出现的次数。


示例 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 <= 105

-109 <= nums[i] <= 109

nums 是一个非递减数组

-109 <= target <= 109


class Solution {
    public int search(int[] nums, int target) {
 
     
    }
}


二、思路讲解


1、方法一

       

暴力查找。


 2、方法二


二分查找改进。题目中的数组是已经排好序的，故而可以想到二分查找。

       

并且，在二分查找的基础上仍可以优化：当左边的数字小于target时，不可能找到了，可以直接break；同理，右边的数字大于target时，也可以直接break。


三、算法描述


1、方法一

       

遍历数组nums，若与target相等，则计数加一。


2、方法二


使用二分查找，若与target相等，则计数加一；一旦左边的指针指向的数小于target、右边的指针指向的数大于target时，可以提前结束。

 

四、Java代码实现


1、方法一


class Solution {
    public int search(int[] nums, int target) {
 
        int count = 0;
        for(int i=0; i<nums.length; i++) {
            if(target == nums[i]) {
                count++;
            }
        }
        return count;
    }
}


 2、方法二 


 if (nums.length == 0) {
            return 0;
        }
        int sum = 0;
        int mid = nums.length >> 2;
        if (nums[mid] == target) {
            sum++;
        }
        int i = mid, j = mid;
        while (i > 0 || j < nums.length - 1) {
            if (i > 0) {
                if (nums[i] >= target) {
                    i--;
                    if (nums[i] == target) {
                        sum++;
                    }
                } else {
                    i = -1;
                }
 
            }
            if (j < nums.length - 1) {
                if (nums[j] <= target) {
                    j++;
                    if (nums[j] == target) {
                        sum++;
                    }
                } else {
                    j = nums.length;
                }
 
            }
 
 
        }
        return sum;


五、时空复杂度分析


1、方法一


        时间复杂度：O(n)        遍历数组nums

        空间复杂度：O(1)


2、方法二


        时间复杂度：O(logn)        二分查找的时间复杂度为logn

        空间复杂度：O(1)

相关文章