算法练习(64): StaticSETofInts(1.4.11

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

知识点

• StaticSETofInts

题目

1.4.11 为 StaticSETofInts （请见表 1.2.15） 添加一个实例方法 howMany()，
找出给定键的出现次数且在最坏情况下所需的运行时间应该和 log(N) 成正比。

1.4.11 Add an instance method howMany() to StaticSETofInts(page99) that finds the number of occurrences of a given key in time proportional to log N in the worst case.

分析

StaticSETofInts的代码如下：

import java.util.Arrays;

public class StaticSETofInts {
    private int[] a;
    public StaticSETofInts(int[] keys) {
        a = new int[keys.length];
        for (int i = 0; i < keys.length; i++)
            a[i] = keys[i]; // defensive copy
        Arrays.sort(a);
    }
    public boolean contains(int key) {
        return rank(key) != -1;
    }
    private int rank(int key) { // Binary search.
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) { // Key is in a[lo..hi] or not present.
            int mid = lo + (hi - lo) / 2;
            if (key < a[mid])
                hi = mid - 1;
            else if (key > a[mid])
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

这道题是上一题：算法练习(63): 修改二分查找算法(1.4.10)的补充，如果做完上一题，就会发现这道题特别简单。我们先回顾一下上一题的代码，最主要的部分是rank函数要改成

public int rank(int key) {
      int hi = a.length;
      int lo = 0;
      int mid = 0;
      while(lo < hi){
            mid = (hi + lo) / 2;
            if (a[mid] < key) {
            lo = mid + 1;
            }else if (a[mid] > key) {
            hi = mid;
            }else if (mid > 0 && a[mid-1] == key) {
            hi = mid;
            }else {
                  return mid;
            }
      }
      
      return -1;
}

其他都是一样的，解决了这个核心问题，我们继续看howMany函数的思路。
我们要先看看是否包含key，如果不包含则howMany函数直接返回0。

答案

public int howMany(int key) {
      int index = rank(key);
      // 如果等于-1 ，那就说明个数为0
      if (-1 == index) {
            return 0;
      }
      int cnt = 0;
      // 再向右边查找，注意避免越界
      while (a[index++] == key) {
            cnt++;
            if (index >= a.length - 1) {
                  break;
            }
      }

      return cnt;
}

测试用例

public static void main(String[] args){
      int[] b = {1,2,3,5,4,5,6,77,7,8,8,9,1,11,22,234,90};
      StaticSETofInts ints = new StaticSETofInts(b);
      //没有这个元素
      int targetKey1 = 111;
      int cnt1 = ints.howMany(targetKey1);
      System.out.println("有"+cnt1+"个"+targetKey1);
      
      //头元素
      int targetKey2 = 1;
      int cnt2 = ints.howMany(targetKey2);
      System.out.println("有"+cnt2+"个"+targetKey2);
      //尾元素
      int targetKey3 = 234;
      int cnt3 = ints.howMany(targetKey3);
      System.out.println("有"+cnt3+"个"+targetKey3);
}

代码索引

StaticSETofInts.java

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。