剑指offer—数字在排序数组中出现次数 解答

剑指offer—数字在排序数组中出现次数

题目描述

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

思路

二分查找三种实现方式解析

对于已经排好序的数组,我们可以使用二分查找法查找指定元素,但是二分查找法有很多种写法,要找到第一次出现的元素,需要使用左边界的查找,找到以后需要遍历其后面的元素,依次累加,知道对应元素不等于k

流程:

  1. 左边界二分查找到第一个元素,保存下标到起始位置,结束位置=起始位置
  2. 往后遍历,累加结束位置
  3. 返回结束位置-起始位置

代码

public class Solution {
    public int GetNumberOfK(int [] nums , int k) {
        if(nums.length==0) return 0;
        int start = 0;
        int end = 0;
        int l = 0;int r = nums.length-1;
        while(l<=r){
            int mid = l + r >> 1;
            if(nums[mid]>=k){
                r = mid - 1;
                if(nums[mid]==k){
                    start = mid;
                    end = start;
                }
            }else{
                l = mid + 1;
            }
        }
        while(end<nums.length&&nums[end]==k){
            end++;
        }
        return end-start;
    }
}

扩展—LeetCode34在排序数组中查找元素的第一个和最后一个位置

题目描述

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值,返回 [-1, -1]。

示例 1:

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

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

思路

与前面剑指offer那题类似,只需要使用一个长度为2的数组保存第一次出现的下标和最后一次出现的下标即可

流程:

  1. 初始化result数组,保存-1用于输出没有找到
  2. 左边界二分查找到第一个元素,保存下标到result[0]
  3. 往后遍历,累加下标
  4. 保存下标result[1]

代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int [] result = new int[]{-1,-1};
        if(nums.length==0) return result;
        int end = -1;
        int l = 0;int r = nums.length-1;
        while(l<=r){
            int mid = l + r >>1;
            if(nums[mid]>=target){
                r = mid - 1;
                if(nums[mid]==target){
                    result[0] = mid;
                    end = mid;
                }
            }else{
                l = mid + 1;
            }
        }
        while(end!=-1&&end+1<nums.length&&nums[end+1]==target){
            end ++;
        }
        result[1] = end;
        return result;
    }
}
  • 本文作者: dzou | 微信:17856530567
  • 本文链接: http://www.dzou.top/post/repeated-counts.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处!
  • 并保留本声明和上方二维码。感谢您的阅读和支持!