算法练习 · 求出等差数列中丢失的那个数

算法练习 · 求出等差数列中丢失的那个数

问题:找出以下等差数列中丢失的那个数

array1

可以看到,上图数组中丢失了4这个元素。那么,如何用程序的手段将它找出来呢

方法一:新建一个bit数组,长度为原数组中的最大值,比如上图数组,最大值为9

    public static void main(String[] args) {
        //有序数组
        Integer[] arr = {1,2,3,5,6,7,8,9};
        //根据元素最大值创建bit数组
        BitSet bitSet = new BitSet(arr[arr.length-1]);
        //循环数组
        for (int i = 0; i < arr.length; i++) {
            //将指定索引设置为true
            bitSet.set(arr[i]);
        }
        //获取为false的索引,便是丢失的那个数字
        System.out.println(bitSet.nextClearBit(1));
    }

方法二:根据差值法寻找

  • 等差数列总和公式 $$\frac{n(n+1)}{2}$$
  • 循环减去数组中的元素
  • 最后得到的结果便是缺失的那个数
    private static void missing2(Integer[] arr){
        //求和
        int sum = gold(arr[arr.length - 1]);
        //循环减去数组中的元素
        for (Integer integer : arr) {
            sum -= integer;
        }
        System.out.println(sum);
    }

    private static int gold(int n){
        return n * (n + 1) / 2;
    }

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×