Leetcode剑指offer53

Posted on Edited on In

LeetCode：剑指 Offer 53

打开网页，突然看到日推是easy难度，本来想就几行代码的事情，弄完了就休息了，提交后–傻了眼–:cry:，居然只打败了6.27%的人，草率了

题目：

剑指 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

限制：

0 <= 数组长度 <= 50000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// first commit
// 执行用时：2 ms, 在所有 Java 提交中击败了6.27%的用户
// 内存消耗：40.8 MB, 在所有 Java 提交中击败了98.84%的用户
class Solution {
    public int search(int[] nums, int target) {
         if(nums==null||nums.length<0){
            return 0;
        }
        int count = 0;
        for (Integer num : nums) {
            if(num>target)break;
            if (target == num)
                count++;
        }
        return count;
    }
}

找到了耗时1ms的答案一看，是foreach替换成了for循环 果然下标访问更快一些

以下贴一个最优解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int search(int[] nums, int target) {
        // 就是left right 更快的定位，总体复杂度差不多，不过
       int left = getRight(nums,target-1);
       int right = getRight(nums,target);
       return right-left;
            
    }
    public int getRight(int[] nums ,int target){
        int left = 0;
        int right = nums.length-1;

        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid]>target){
                right = mid-1;
            }
            else if(nums[mid]<=target){
                left = mid + 1;
            }
        } 
        return left;
    }
    
}