這次主要是把現(xiàn)實中項目的真實案例拿出來，使用算法改進其中的有缺陷的部分。

項目中功能背景和代碼

之前看過同事寫了一個生成會議號問題的代碼，情況是這樣的，會議號有個固定范圍比如10位數(shù)，隨機生成一個號碼，這個號碼如果已經(jīng)存在，就再生成，直到生成的號碼不存在為止。這里偽代碼大概是這樣的

boolean flag = false;
do {
  long random = new Random().nextInt(1000000000);
  flag = redis.checkExistsNumber(random);//匹配redis是否存在這個號碼
} while(flag)

像這樣的代碼，while循環(huán)多少次才能得到結(jié)果。

改進算法：

于是有了下面的改進算法：
算法思路是這樣的，假如：
100個數(shù)字，其中3,5,23,24,35這些是已經(jīng)用過的數(shù)字，現(xiàn)在隨機獲取一個數(shù)字。
1,2,99,4,98...95 從左往右，碰到一個已經(jīng)存在的數(shù)字的時候，就從末尾取一個數(shù)字出來填到這個存在的位置，這樣隨機數(shù)范圍1-95，如果隨機出3就返回99，這樣一次隨機就可以得到結(jié)果。

    public static void main(String[] args) {

        NumberUtil blacklist = new NumberUtil();
//        int[] arr = new int[]{3,5,23,24,35};
        int[] arr = new int[100000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt(arr.length);
        }
        log.debug("arr={}", arr);
        for (int i = 0; i < 1000; i++) {
            long s = System.currentTimeMillis();
            blacklist.build(1000000000, arr);
            Integer integer = blacklist.genNumber();
            long e = System.currentTimeMillis();
            log.debug("time={}  value={}", e-s, integer);
        }
    }


public class NumberUtil {
        private int max;
        private Map<Integer, Integer> map = new HashMap<>();

        public void build(int n, int[] blacklist) {
            Arrays.sort(blacklist);
            int m = blacklist.length;
            for (int i = 0; i < m && blacklist[i]<n; i++) {
                for (n--; n > blacklist[i]; n--) {
                    if (n==blacklist[m-1]) {
                        m--;
                    } else {
                        map.put(blacklist[i], n);
                        break;
                    }
                }
            }
            max = n;
        }

        public Integer genNumber() {
            Integer random = new Random().nextInt(max);
            log.debug("random={}", random);
            return map.containsKey(random)?map.get(random):random;
        }
    }