算法热题:在排序数组中查找数字 I
每日简短一刷,保持手感系列
题目:统计一个数字在排序数组中出现的次数。
示例 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
就单单看题目,这道理逻辑非常直白和简单,查到一个数字在排序数组中出现的次数,直接遍历一次统计就完了
classSolution{
publicintsearch(int[] nums, int target){
int cnt = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) cnt++;
}
return cnt;
}
}
时间复杂度 O(n),空间复杂度 O(1)
但是这不免也太简单了吧?
所以要注意提示,nums 是一个非递减数组,从这个提示可以得知它是一个有序数组,看到有序二字就该有应激反应:二分法。
不过这不是朴素二分,而是二分的变型。
按照题意我们应该利用二分找到和 target 相等的数组最左位置,然后之后有两个选择
根据这个最左位置直接往后遍历 再通过二分找到和 target 相等的数组最右位置
如果你选择第一种,其实时间复杂度还是变成了 O(n)。
所以我们选择第二种,继续利用变型的二分找到最后的位置,最终最右的位置减去最左的位置再+1得到的值就是重复的次数。
让我们看一下代码:
classSolution{
publicintsearch(int[] nums, int target){
int len = nums.length;
if (len == 0) { //空数组直接返回,不然下面 nums[left] 就抛错了。
return0;
}
int left = 0, right = len-1;
//先二分找到最左节点
while(left < right) {
int mid = left + right >> 1;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
// 说明没找到,直接返回 0
if (nums[left] != target) {
return0;
}
int rightLeft = left;
right = len - 1;
//二分找到最右节点
while (left < right) {
int mid = left + right + 1 >> 1; //二分边界处理,不然会死循环
if (nums[mid] <= target) {
left = mid;
} else {
right = mid - 1;
}
}
return right - rightLeft + 1;
}
}
相信思路还是挺简单的,但是十个二分九个错,所以二分的细节还是需要特意去画画的,不然容易出错,之后我再专门写一篇分析分析二分的变型。
一道简单题,可点击原文进行练习。
关键词
数组
算法
nums.length
数字
位置
最新评论
推荐文章
作者最新文章
你可能感兴趣的文章
Copyright Disclaimer: The copyright of contents (including texts, images, videos and audios) posted above belong to the User who shared or the third-party website which the User shared from. If you found your copyright have been infringed, please send a DMCA takedown notice to [email protected]. For more detail of the source, please click on the button "Read Original Post" below. For other communications, please send to [email protected].
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。
版权声明:以上内容为用户推荐收藏至CareerEngine平台,其内容(含文字、图片、视频、音频等)及知识版权均属用户或用户转发自的第三方网站,如涉嫌侵权,请通知[email protected]进行信息删除。如需查看信息来源,请点击“查看原文”。如需洽谈其它事宜,请联系[email protected]。