【LeetCode刷题】剑指 Offer 53 - I. 在排序数组中查找数字 I


题目链接:剑指 Offer 53 - I. 在排序数组中查找数字 I

题目

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

 

示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2

示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0

解题

一上来的方法

显然一个循环可以解决问题,时间复杂度$$O(n)$$

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

提交这个代码之后对性能并不满意,于是想改进一下。

改进(二分法)

注意到题目中提到了排序数组,数组是有序的,于是我便想到了折半查找,$$O(log n)$$的复杂度,好令人心动,说干就干,大体思路是:
先折半查找target值,如果找到,循环遍历查找的值的左边和右边(以第一个查找到的target为中心的邻域),统计目标值个数,找不到直接返回0。
正如折半查找的作者所说:“二分查找思想很简单,但细节是魔鬼。”,代码我反反复复改了好几次小细节,才最终通过。
提交记录
一开始忘记了return结束循环超时,后面几次又因为左右边界问题导致越界、漏算,最终,终于成功通过。

具体实现

class Solution {
    public int search(int[] nums, int target) {
        if (nums.length == 1)
            return nums[0] == target ? 1 : 0;
        else if (nums.length == 0)
            return 0;

        int low = 0, high = nums.length - 1;
        int sum = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] == target) {
                int t = mid - 1;
                while (mid <= high && nums[mid] == target) {
                    ++sum;
                    ++mid;
                }
                while (t >= low && nums[t] == target) {
                    ++sum;
                    --t;
                }
                return sum;
            } else if (nums[mid] > target)
                high = mid - 1;
            else {
                low = mid + 1;
            }
        }

        return sum;
    }
}

声明:楓の街|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 【LeetCode刷题】剑指 Offer 53 - I. 在排序数组中查找数字 I


Just For Fun...