开发者社区> 游客udktoj33qi3xe> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

每日一练(24):在排序数组中查找数字

简介: 统计一个数字在排序数组中出现的次数。
+关注继续查看

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


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


来源:力扣(LeetCode)


链接:https://leetcode-cn.com/probl...


方法一:STL(一行搞定)


count函数可以用来统计字符串中某个字符的个数


使用方法是count(ivec.begin() , ivec.end() , searchValue),其中begin指的是起始地址,end指的是结束地址,第三个参数指的是需要查找的字符。


int search(vector<int>& nums, int target) {
    return count(nums.begin(),nums.end(),target);
}


方法二:暴力解法



直接for循环遍历查找目标并计数


int search(vector<int>& nums, int target) {
    if (nums.size() == 0) {
        return 0;
    }
    if (nums.size() == 1) {
        if (nums[0] == target) {
            return 1;
        } else {
            return 0;
        }
    }
    int count = 0;
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] == target) {
            count++;    //循环计数
        }
    }
    return count;
}


方法三:二分查找


二分模板:


模板1


当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时,其更新操作是r = mid或者l = mid + 1,计算mid时不需要加1,即mid = (l + r)/2。


int bsearch_1(int l, int r)
{
    while (l < r)
    {
        int mid = (l + r)/2;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}


模板2


当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时,其更新操作是r = mid - 1或者l = mid,此时为了防止死循环,计算mid时需要加1,即mid = ( l + r + 1 ) /2。


int bsearch_2(int l, int r)
{
    while (l < r)
    {
        int mid = ( l + r + 1 ) /2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}


  • lowerBound(target)
  • upper(target+1)


时间复杂度分析: 两次二分查找的时间复杂度为 O(logn)。


空间复杂度分析: 没有使用额外的数组,因此空间复杂度为O(1)。


int lowerBound(vector<int>& nums, int target) {
    int l, r;
    l = 0;
    r = nums.size();
    while (l < r) {
        int mid = (l + r) >> 1;
        if (target <= nums[mid]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}
int search(vector<int>& nums, int target) {
    int lower = lowerBound(nums, target);
    int upper = lowerBound(nums, target + 1);
    return (upper - lower);
}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
力扣每日一题:374.猜数字大小 python二分查找的基础公式!
力扣每日一题:374.猜数字大小 python二分查找的基础公式!
35 0
每日一练(25): 0~n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字
14 0
每日一练(45):长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
17 0
每日一练(7):旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
23 0
数组中重复的数字(C语言/C++)
数组中重复的数字(C语言/C++)
33 0
JS中数组排序
JS中数组排序
804 0
二维数组的查找
题目:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。        当我们需要解决一个复杂的问题时,一个很有效的办法就是从一个具体的问题入手,通过分析简单具体的例子,试图寻找普遍的规律。
413 0
111
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载