0%

Leetcode剑指offer53

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;
}

}