数字在升序数组中出现的次数_37

名字是乱打的

发布于 2021-12-23 18:24:37

3260

发布于 2021-12-23 18:24:37

文章被收录于专栏：软件工程

看到升序数组，那一般来说二分法跑不了那么这里我提供下我的三种解法，两种二分法，一种hash存储；

1 .两次二分法分别找到第一次出现的该数字和最后一次出现的该数字位置

主要思路，在二分法第一次查到k值的时候判断前面或者后面是否有也等于k值的，以此决定是否要前移或者后移来找到最左或者最右的k值点；代码：

public class Solution {
    //统计一个数字在排序数组中出现的次数
    public int GetNumberOfK(int[] array, int k) {
         if (array == null) {
            return 0;
        }
        if (array.length==1&&array[0]==k){
            return 1;
        }
        int firstKIndex = getFirstKIndex(array, k);
        int lastKIndex = getLastKIndex(array, k);
        return firstKIndex==lastKIndex?0:lastKIndex-firstKIndex+1;
    }
    public int getFirstKIndex(int[] array, int k){//得到第一个k---右结点向左移动
        int left = 0, right = array.length - 1;
        int mid = getMid(left, right);
        while (left <= right) {
            if (array[mid] == k&&mid - 1 >= 0 && array[mid - 1] == k) {
                right=mid-1;
            } else if (array[mid]> k) {
                right = mid-1;
            } else if (array[mid] < k) {
                left = mid+1;
            }else {
                return mid;
            }
            mid = getMid(left, right);
        }
        return -1;
    }
    public int getLastKIndex(int[] array, int k){//得到第一个k---左结点向右移动
        int left = 0, right = array.length - 1;
        int mid = getMid(left, right);
        while (left <= right) {
            if (array[mid] == k&&mid + 1<=array.length-1&& array[mid + 1] == k) {
                left=mid+1;
            } else if (array[mid]> k) {
                right = mid-1;
            } else if (array[mid] < k) {
                left = mid+1;
            }else {
                return mid;
            }
            mid = getMid(left, right);
        }
        return -1;
    }

    public int getMid(int left, int right) {
        return  left+ (right + left) / 2;
    }
}

2. 查找k-0.5和k+0.5来获取这两者之间的数字个数就是k的个数

因为array中都是整数，所以可以稍微变一下，不是搜索k的两个位置，而是搜索k-0.5和k+0.5 这两个数应该插入的位置，然后相减即可。

代码：

  public int GetNumberOfK(int [] array , int k) {
        if (array==null||array.length<1){
            return 0;
        }
        return binarySearch(array,k+0.5)-binarySearch(array,k-0.5);
    }

    private int binarySearch(int[] array, double k) {
        int low=0,high=array.length-1;
        while (low<=high){
            int mid=getMidIndex(low,high);
            if (k<array[mid]){
                high=mid-1;
            }else if (k>array[mid]){
                low=mid+1;
            }
        }
        return low;
    }

    public int getMidIndex(int left,int right){
        return left+(right-left)/2;
    }

3.hash

没啥好说的，就是一个普通利用hash随机读取

 public int GetNumberOfK(int [] array , int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
         
        for (int num : array) {
            if (num == k) {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
        }
         
        return map.get(k) == null ? 0 : map.get(k);
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/4/28 上，如有侵权请联系 cloudcommunity@tencent.com 删除

hash