首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >剑指Offer LeetCode 面试题53 - I. 在排序数组中查找数字 I

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

作者头像
手撕代码八百里
发布于 2020-07-28 15:27:26
发布于 2020-07-28 15:27:26
62800
代码可运行
举报
文章被收录于专栏:猿计划猿计划
运行总次数:0
代码可运行

面试题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

简单暴力解法

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
class Solution {
    public int search(int[] nums, int target) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==target){
                sum++;
            }
        }
        return sum;
    }
}

二分查找

因为数组是已经排序好的数组,所以可以先找出左右边界,找到数组中的左右边界,然后相减就可以拿到这个数字了.

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
/**
 * @Auther: truedei
 * @Date: 2020 /20-5-20 08:45
 * @Description:
 */
public class Test1 {

    static  public int search(int[] nums, int target) {


        int i=0;
        int j=nums.length-1;
        int left=0,right=0;

        //搜索左边界
        while (i<=j){
            int mid =  (i + j) /2;

            if(nums[mid] <= target)
                i = i + 1;
            else
                j = j - 1;
        }

        right = i;

        i = 0;
        j=nums.length-1;

        //搜索右边界
        while (i<=j){
            int mid =  (i + j) /2;

            if(nums[mid] < target)
                i = i + 1;
            else
                j = j - 1;
        }

        left=j;

        return right - left - 1;
    }

    public static void main(String[] args) {
        int nums[] = new int[]{5,7,7,8,8,10},target = 8;


        System.out.println(search(nums,target));
    }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/05/25 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
LeetCode-面试题53-1-在排序数组中查找数字I
在有序的数组中二分查找,确定第一个k出现的位置和最后一个k出现的位置,然后两个位置相减即是出现次数
benym
2022/07/14
6220
剑指Offer - 面试题53 - I. 在排序数组中查找数字 I(二分查找的变形版本)
类似题目:LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)
Michael阿明
2020/07/13
9860
剑指Offer - 面试题53 - I. 在排序数组中查找数字 I(二分查找的变形版本)
LeetCode-34-在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
benym
2022/07/14
2.7K0
Leetcode算法【34在排序数组中查找元素】
在之前ARTS打卡中,我每次都把算法、英文文档、技巧都写在一个文章里,这样对我的帮助是挺大的,但是可能给读者来说,一下子有这么多的输入,还是需要长时间的消化。
程序员小跃
2019/12/27
3.2K0
图解LeetCode——剑指 Offer 53 - I. 在排序数组中查找数字 I
首先,根据题目描述,我们可以得知题目给我们的数组nums是一个有序的数组,那么针对这个特性我们可以得出结论,即:相同的数字会紧密的排列在一起。所以,根据这个结论,我们可以采用双指针来解决这个问题,步骤如下所示:
爪哇缪斯
2023/05/10
4070
图解LeetCode——剑指 Offer 53 - I. 在排序数组中查找数字 I
二分查找总结
二分查找是在每次匹配后,将查找的空间一分为二的算法,二分查找应该是有序的数组进行查找.
Tim在路上
2020/08/04
4970
剑指Offer题解 - Day6
首先考虑通过遍历数组进行查找重复次数。该方法没有合理利用有序数组的前提条件,适合无序数组的元素统计。
chuckQu
2022/08/19
1580
【剑指offer:在排序数组中查找数字】搜索左右边界:从两边向中间、二分查找
二分查找一般用来查找数字在有序数组中是否出现过。进一步想,它可以用来不断在子序列中搜索对应数字。所以,我们就可以用它来向左边子序列中不断搜索,确认左边界;同样的思路,确认右边界。
心谭博客
2020/04/21
1.6K0
LeetCode通关:数组十七连,真是不简单
数组基本上是我们最熟悉的数据结构了,刚会写“Hello World”不久,接着就是“杨辉三角”之类的练习。
三分恶
2021/08/10
4260
【优先算法】不知OJ谁裁出,二分查找似剪刀 - 二分查找算法
题目链接: 704. 二分查找 题目描述: 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
用户11369350
2024/12/24
930
【优先算法】不知OJ谁裁出,二分查找似剪刀 - 二分查找算法
【剑指Offer】53.1在排序数组中查找数字 I
NowCoder 题目描述 统计一个数字在排序数组中出现的次数 Input: nums = 1, 2, 3, 3, 3, 3, 4, 6 K = 3 Output: 4 解题思路 class Solution { public int search(int[] nums, int target) { if(nums == null || nums.length == 0) return 0; // 二分 i
瑞新
2020/12/07
1.2K0
leetcode34-在排序数组中查找元素的第一个和最后一个位置
今天刷的题目是:在排序数组中查找元素的第一个和最后一个位置,这道题目在最开始AC以后,然后做了两步的优化操作,供大家参考。
乔戈里
2019/09/17
3.1K0
leetcode34-在排序数组中查找元素的第一个和最后一个位置
【算法题解】 Day20 查找
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
sidiot
2023/08/26
3010
【剑指offer|5.在排序数组中查找数字I】
0.在排序数组中查找数字I 1.低效率方法© 通过二分查找找到目标值, 局部时间复杂度O(logN); 然后在目标值左右扫描, 直到分别扫描到第一个3和最后一个3, 因为要查找的数字在长度为N的数组中可能出现N次, 所以局部时间复杂度O(N); 总体时间复杂度O(N),效率很低,和直接遍历扫描数个数的笨方法时间复杂度相同O(N),不可取 int BinarySearch(int* nums, int numsSize, int target) { int left = 0, ri
MicroFrank
2023/04/12
1.1K0
【剑指offer|5.在排序数组中查找数字I】
搞定大厂算法面试之leetcode精讲5.二分查找
搞定大厂算法面试之leetcode精讲5.二分查找 视频教程(高效学习):点击学习 目录: 1.开篇介绍 2.时间空间复杂度 3.动态规划 4.贪心 5.二分查找 6.深度优先&广度优先 7.双指针 8.滑动窗口 9.位运算 10.递归&分治 11剪枝&回溯 12.堆 13.单调栈 14.排序算法 15.链表 16.set&map 17.栈 18.队列 19.数组 20.字符串 21.树 22.字典树 23.并查集 24.其他类型题 二分搜索 时间复杂度O(logn) 步骤: 从数组中间的元素开始,如果中
全栈潇晨
2021/11/24
3540
剑指offer | 面试题8:旋转数组的最小数字
如下图所示,寻找旋转数组的最小元素即为寻找 右排序数组 的首个元素 nums[x] ,称 x 为 旋转点 。
千羽
2021/12/29
2580
剑指offer | 面试题8:旋转数组的最小数字
在排序数组中查找元素的第一个和最后一个位置(leetcode34)
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
Vincent-yuan
2021/04/09
2.1K0
在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
代码随想录
2021/12/15
5.7K0
【算法】——二分查找合集
巧妙记忆:循环条件为while(left<right)时,left = mid,想象一下,只剩下两个球,那么我们的mid只能落在右端点,否则left = mid 会造成 left < right 死循环,此时我们确定的是右边的界限
三三是该溜子
2024/12/30
1080
【算法】——二分查找合集
LeetCode-33-搜索旋转排序数组
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
benym
2022/07/14
2660
推荐阅读
相关推荐
LeetCode-面试题53-1-在排序数组中查找数字I
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档