代码编织梦想

剑指 Offer 53 - I. 在排序数组中查找数字 I

直达链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/

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

示例 1:

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

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

解题思路:

1、暴力法:

        (1) 因为是已经排序,先用target比较数组的第一个元素和最后一个元素判断查找的元素是否存在,如果不存在直接返回0

        (2) 定义一个标记数count,遍历整个数组,当数组中的元素和target相同,count+1

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

时间、空间复杂度:

2、二分查找:

        (1)两次二分查找

由于数组已经排序,因此整个数组是单调递增的,可以利用二分法来加速查找的过程。首先找到第一个出现target的位置left,其次找到第一个比target大的数的位置right,right-left+1就得到出现次数。 关键:如何找到第一个target出现的位置

二分查找中,寻找 leftIdx 即为在数组中寻找第一个大于等于target 的下标,寻找 rightIdx 即为在数组中寻找第一个大于 target 的下标,然后将下标减一。两者的判断条件不同,为了代码的复用,我们定义 binarySearch(nums, target, lower) 表示在nums 数组中二分查找target 的位置,如果 ower 为true,则查找第一个大于等于arget 的下标,否则查找第一个大于target 的下标。因为target 可能不存在数组中,因此我们需要重新校验我们得到的两个下标 leftIdx 和 rightIdx,看是否符合条件,如果符合条件就返回rightIdx-leftIdx+1,不符合就返回 0。

参考链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-wl6kr/

class Solution {
    public int search(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return rightIdx - leftIdx + 1;
        } 
        return 0;
    }
    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

时间、空间复杂度:

(2)二分单边+线性扫描

二分查找,找到目标值 target 「首次」出现或者「最后」出现的下标,然后「往后」或者「往前」进行数量统计。

参考链接:

class Solution {
    public int search(int[] nums, int t) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {     //二分查找最后出现位置
            int mid = (l + r + 1)/2;
            if (nums[mid] <= t) 
                l = mid;
            else 
                r = mid - 1;
        }
        int ans = 0;//向前遍历
        while (r >= 0 && nums[r] == t && r-->= 0) 
            ans++;
        return ans;
    }
}

时间、空间复杂度:

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/aoocean/article/details/118817292

搜索位置插入_震逗比的博客-爱代码爱编程

搜索插入位置 题目 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 你可以假设数组中无重复元素。 示例 1: 输入: [1,3,5,6

【剑指offer】面试题53 - 1:在排序数组中查找数字 I(java)-爱代码爱编程

统计一个数字在排序数组中出现的次数。   示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0   限制: 0 <= 数组长度 <= 50000   代码: class Soluti

剑指offer 面试题53 - I. 在排序数组中查找数字 I [简单]-爱代码爱编程

我的解题: 1.先用二分查找找到target,在由该节点向左右遍历看有多少相等的 class Solution { public: int search(vector<int>& nums, int target) { int i=0; int j=nums.size()-1;

剑指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 排序里面查找数字,首先就想到是二分,查出现次数,显然是找左边界

LeetCode(剑指offer-Array)-面试题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 链接:https://leetcode-c

剑指 Offer 53-I. 在排序数组中查找数字 I(Java版本)-爱代码爱编程

剑指 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 <= 数组长度 <= 50

剑指 Offer 53 - I. 在排序数组中查找数字 I - leetcode 剑指offer系列-爱代码爱编程

题目难度: 简单 原题链接 今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号 每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了 题目描述 统计一个数字在排序数组中出现的次数。 0 <= 数组长度 <= 5

python--剑指offer--简单--53 - I. 在排序数组中查找数字 I-爱代码爱编程

from typing import List class Solution: def search(self, nums: List[int], target: int) -> int: if not nums: return 0 l, r = 0, len(nums)-1

LeetCode:剑指 Offer 53 - I. 在排序数组中查找数字 I(C语言)-爱代码爱编程

题目描述: 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 限制: 0 <= 数组长度 <= 50000 作者:Krahets 链接:http

每日一题:剑指 Offer 53 - I. 在排序数组中查找数字 I-爱代码爱编程

每日一题:剑指 Offer 53 - I. 在排序数组中查找数字 I 1、题目 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 限制: 0 <

论遇到的一个非常无语的基础语法问题-爱代码爱编程

关于代码与数学公式区别的问题 前一阵子做一个算法题,题目是比较简单的,大概是把一个数组从中间位置断开将后半部分与前半部分对调,然后查找指定值的索引,也就没想那么多,然后快速写完提交,结果运行结果错误。。。 仔细查找了半天,就是找不到问题,被迫之下只能debug,然后让我十分惊奇的一幕发生了,for循环被跳了,上代码。 main() int targ

二分查找上界和下界(不含target)-爱代码爱编程

二分法(这里采用左闭右闭) public int search(int[] nums, int target) { int left=0; int right=nums.length-1; int middle; while(left<=right){ mi

剑指 Offer 53 - I. 在排序数组中查找数字 I 【 c++/java详细题解 】-爱代码爱编程

目录 1、题目2、思路3、c++代码4、java代码 1、题目 统计一个数字在排序数组中出现的次数。 示例 1: 输入: nums = [5,7,7,8,8,10], target = 8 输出: 2 示例 2: 输入: nums = [5,7,7,8,8,10], target = 6 输出: 0 提示: 0 <= n

【LeetCode - Java】190. 颠倒二进制位 (简单)-爱代码爱编程

目录 1. 题目描述2. 解题思路3. 代码实现3.1 数值运算(C语言版)3.2 数值运算3.3 二进制运算逐位逆转3.3 对比 1. 题目描述 2. 解题思路 题目明确这是二进制位的运算,那么我们就得从常数转换为二进制入手。最常规的方法,把常数除二取余然后直接乘对应的位权,完事了。对于C语言来说,确实是这样子的,因为在C语言当中有无

【LeetCode 14】454.四数相加 II-爱代码爱编程

454.四数相加 II 文章目录 454.四数相加 II一、题意二、思考过程2.1定义一个unordered_map2.2遍历nums1、nums2数组,统计两个数组的元素之和及出现的次数,并放到map中2.3定义int类型的变量count,用来统计a+b+c+d=0出现的次数2.4在遍历nums3、nums4数组,如果(0-(c+d))在map

力扣 76题 最小覆盖子串(双指针 + 滑动窗口)-爱代码爱编程

76. 最小覆盖子串 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。如果 s 中存在这样的子串,我们保证它是唯一的答案。     提示: 1 <

LeetCode每日一题(22年1月27日-2月5日)-爱代码爱编程

目录(每日一题) 2047. 句子中的有效单词数1996. 游戏中弱角色的数量1765. 地图中的最高点884. 两句话中的不常见单词1342. 将数字变成 0 的操作次数1763. 最长的美好子字符串2000. 反转单词前缀1414. 和为 K 的最少斐波那契数字数目1725. 可以形成最大正方形的矩形数目1219. 黄金矿工 2047. 句