算法趣题——寻找缺失整数

算法 Java

算法趣题一则

题目：寻找缺失整数
扩展一：寻找唯一出现奇数次的整数
扩展二：寻找两个出现奇数次的整数
测试代码

几天前在伯乐在线看到一篇漫画算法文章《漫画算法：找出缺失的整数》，画风十分诙谐有趣。虽然题目并不难，但解法的逐步深入对自己的基础梳理仍有较大帮助，最后的异或算法更是精华。现将题目整理于此，并附上自己的代码，仅供参考学习之用。

Leetcode原题及其扩展请移步——
Leetcode 136.Single Number
Leetcode 137.Single Number II

题目：寻找缺失整数

一个无序数组里有99个不重复正整数，范围从1到100，唯独缺少一个整数。如何找出这个缺失的整数？

解法1：使用HashMap

创建一个HashMap，以1到100为键，值都是0。然后遍历整个数组，每读到一个整数，就找到HashMap当中对应的键，让其值加1。

由于数组中缺少一个整数，最终一定有99个键对应的值等于1，剩下一个键对应的值等于0。遍历修改后的HashMap，找到这个值为0的键。

假设数组长度为N，那么该解法的时间复杂度为O(N)，空间复杂度为O(N)

public int getMissingDigitByHash(ArrayList<Integer> list) {
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(list.size() + 1);
    for (int i : list) {
        map.put(i, 1);
    }
    for (int i = 1; i < list.size() + 2; i++) {
        if (!map.containsKey(i)) return i;
    }
    return -1;
}

该解法在时间上是最优的，但额外开辟了空间——怎样才能够降低空间复杂度呢？

解法2：排序后遍历

先把数组元素进行排序，然后遍历数组，检查任意两个相邻元素数值是否是连续的。如果不连续，则中间缺少的整数就是所要寻找的；如果全部连续，则缺少的整数不是1就是100。

假设数组长度为N，如果用时间复杂度为O(N*LogN)的排序算法进行排序，那么该算法的时间复杂度为O(N*LogN)，空间复杂度为O(1)。

public int getMissingDigitBySort(ArrayList<Integer> list) {
    Collections.sort(list);
    if (list.get(0) > 1) {
        return 1;
    }
    for (int i = 0; i < list.size() - 1; i++) {
        if (list.get(i + 1) - list.get(i) > 1) {
            return list.get(i) + 1;
        }
    }
    return list.size() + 1;
}

这种解法没有开辟额外空间，但是时间复杂度又加大了。有办法让时间和空间都优化吗？

解法3：求和后逐个减去

很简单也很高效的方法，先算出1+2+3+……+100的和，然后依次减去数组里的元素，最后的到的差，就是唯一缺失的整数。

假设数组长度为N，那么该解法的时间复杂度为O(N)，空间复杂度为O(1)

public int getMissingDigitBySum(ArrayList<Integer> list) {
    int result = 0;
    for (int i = 0; i < list.size() + 2; i++) {
        result += i;
    }
    for (int i : list) {
        result -= i;
    }
    return result;
}

对于没有重复元素的数组，该解法在时间和空间上已经是最优了。接下来扩展该问题——

扩展一：寻找唯一出现奇数次的整数

一个无序数组里有若干个正整数，范围从1到100，其中99个整数都出现了偶数次，只有一个整数出现了奇数次（比如1,1,2,2,3,3,4,5,5），如何找到这个出现奇数次的整数？

遍历整个数组，依次做异或运算。由于异或在位运算时相同为0，不同为1，因此所有出现偶数次的整数都会相互抵消变成0，只有唯一出现奇数次的整数会被留下。

假设数组长度为N，那么该解法的时间复杂度为O(N)，空间复杂度为O(1)

public int getMissingDigitByXor(int[] arr) {
    int result = 0;
    for (int i : arr) {
        result ^= i;
    }
    return result;
}

继续扩展，如果数组里有两个整数出现奇数次，而不是一个，如何找出这两个整数？

扩展二：寻找两个出现奇数次的整数

一个无序数组里有若干个正整数，范围从1到100，其中98个整数都出现了偶数次，只有两个整数出现了奇数次（比如1,1,2,2,3,4,5,5），如何找到这个出现奇数次的整数？

遍历整个数组，依次做异或运算。由于数组存在两个出现奇数次的整数，所以最终异或的结果等同于这两个整数的异或结果（其余部分互相抵消）。这个结果中，至少会有一个二进制位是1;如果都是0，说明两个数相等，和题目不符

举个例子，如果最终异或的结果为5，转换成二进制是 00000101 。此时我们可以选择任意一个是1的二进制位来分析，比如末位。把两个奇数次出现的整数命名为A和B，如果末位是1，说明A和B转为二进制的末位不同，必定其中一个整数的末位是1，另一个整数的末位是0。

根据这个结论，我们可以把原数组按照二进制的末位不同，分成两部分：一部分的末位是1，另一部分的末位是0。由于A和B的末位不同，所以A在其中一部分，B在另一部分，绝不会出现A和B在同一部分，另一部分没有的情况。

这样一来就会发现，问题又回归到了上一题的情况，按照原先的异或解法，从每一部分中找出唯一的奇数次整数即可。

假设数组长度为N，那么该解法的时间复杂度为O(N)。把数组分成两部分，并不需要借助额外的存储空间，完全可以在按二进制分组的同时来做异或运算，所以空间复杂度仍然是O(1)。

public int[] getMissingDigitsByXor(int[] arr) {
    int A = 0;
    int B = 0;
    int result = getMissingDigitByXor(arr);
    //find out which index have 1
    String binResult = Integer.toString(result, 2);
    //System.out.println("Bin result:" + binResult);
    int index = binResult.lastIndexOf("1");
    int numShift = binResult.length() - index - 1;
    //System.out.println("Num shift: " + numShift);
    for (int i : arr) {
        //仅对选取的二进制位为1的整数进行异或
        A = (((i >> numShift) & 1) == 1) ? (A ^ i) : A;
        //仅对选取的二进制位位0的整数进行异或
        B = (((i >> numShift) & 1) == 0) ? (B ^ i) : B;
    }
    return new int[]{A, B};
}

测试代码

下面是自己写的测试代码，有兴趣的可以Copy到本地运行一下，如有错误还请不吝指正 : )

import java.util.*;
//Created by AbelSu on 2016/10/17.
public class MissingDigit {
    //定义数组长度
    private static final int SIZE = 100;
    //扩展一中的数组
    private static final int[] arr1 = {5, 1, 4, 2, 1, 3, 2, 5, 3};
    //扩展二中的数组
    private static final int[] arr2 = {4, 3, 1, 2, 2, 5, 1, 5};
    public static void main(String[] args) {
        //生成99个随机整数测试数组，范围1-100，彼此互不相同
        ArrayList<Integer> list = new ArrayList<Integer>();
        Random random = new Random();
        int missingDigit = random.nextInt(SIZE);
        for (int i = 1; i < 101; i++) {
            if (i != missingDigit) {
                list.add(i);
            }
        }
        Collections.shuffle(list);
        //题目：寻找缺失整数
        System.out.println("题目：一个无序数组里有99个不同的正整数，范围1-100，如何找到这个缺失的整数？\n\n" + list + "\n");
        System.out.println("解法1： 使用HashMap,时间复杂度O(N),空间复杂度O(N)：" + getMissingDigitByHash(list) + "\n");
        System.out.println("解法2： 排序后遍历,时间复杂度O(N*logN),空间复杂度O(1)：" + getMissingDigitBySort(list) + "\n");
        System.out.println("解法3： 求和后逐个减去，时间复杂度O(N),空间复杂度O(1): " + getMissingDigitBySum(list) + "\n");
        //扩展一：寻找唯一出现奇数次的整数
        System.out.println("扩展一：一个无序数组里有若干个正整数，范围1-100，其中99个整数都出现了偶数次，只有一个整数出现了奇数次，如何找到这个出现奇数次的整数？\n");
        System.out.print("[");
        for (int i = 0; i < arr1.length - 1; i++) {
            System.out.print(arr1[i] + ", ");
        }
        System.out.print(arr1[arr1.length - 1] + "]\n\n");
        System.out.println("解法：遍历整个数组，依次做异或运算，结果即为出现奇数次的整数：" + getMissingDigitByXor(arr1) + "\n");
        //扩展二：寻找两个出现奇数次的整数
        System.out.println("扩展二：一个无序数组里有若干个正整数，范围从1到100，其中98个整数都出现了偶数次，只有两个整数出现了奇数次，如何找到这个出现奇数次的整数？\n");
        System.out.print("[");
        for (int i = 0; i < arr2.length - 1; i++) {
            System.out.print(arr2[i] + ", ");
        }
        System.out.print(arr2[arr2.length - 1] + "]\n\n");
        System.out.print("解法：遍历整个数组，依次做异或运算。根据二进制结果中为1的位划分为两部分，再按上一题解法求解：");
        int[] result = getMissingDigitsByXor(arr2);
        for (int i : result) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    //解法1：使用HashMap
    public static int getMissingDigitByHash(ArrayList<Integer> list) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(list.size() + 1);
        for (int i : list) {
            map.put(i, 1);
        }
        for (int i = 1; i < list.size() + 2; i++) {
            if (!map.containsKey(i)) return i;
        }
        return -1;
    }
    //解法2：排序后遍历
    public static int getMissingDigitBySort(ArrayList<Integer> list) {
        Collections.sort(list);
        if (list.get(0) > 1) {
            return 1;
        }
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i + 1) - list.get(i) > 1) {
                return list.get(i) + 1;
            }
        }
        return list.size() + 1;
    }
    //解法3：求和后逐个减去
    public static int getMissingDigitBySum(ArrayList<Integer> list) {
        int result = 0;
        for (int i = 0; i < list.size() + 2; i++) {
            result += i;
        }
        for (int i : list) {
            result -= i;
        }
        return result;
    }
    //扩展一：寻找唯一出现奇数次的整数
    public static int getMissingDigitByXor(int[] arr) {
        int result = 0;
        for (int i : arr) {
            result ^= i;
        }
        return result;
    }
    //扩展二：寻找两个出现奇数次的整数
    public static int[] getMissingDigitsByXor(int[] arr) {
        int A = 0;
        int B = 0;
        int result = getMissingDigitByXor(arr);
        //find out which index have 1
        String binResult = Integer.toString(result, 2);
        //System.out.println("Bin result:" + binResult);
        int index = binResult.lastIndexOf("1");
        int numShift = binResult.length() - index - 1;
        //System.out.println("Num shift: " + numShift);
        for (int i : arr) {
            A = (((i >> numShift) & 1) == 1) ? (A ^ i) : A;
            B = (((i >> numShift) & 1) == 0) ? (B ^ i) : B;
        }
        return new int[]{A, B};
    }
}

算法趣题——寻找缺失整数

Table of Contents

题目：寻找缺失整数

解法1：使用HashMap

解法2：排序后遍历

解法3：求和后逐个减去

扩展一：寻找唯一出现奇数次的整数

扩展二：寻找两个出现奇数次的整数

测试代码

Abel Su

算法趣题——寻找缺失整数

Table of Contents

题目：寻找缺失整数

解法1：使用HashMap

解法2：排序后遍历

解法3：求和后逐个减去

扩展一：寻找唯一出现奇数次的整数

扩展二：寻找两个出现奇数次的整数

测试代码

Abel Su

我有故事，你有酒吗？

今夕何夕，湫兮如风

SAP ABAP 基本语句

SAP ABAP 数据类型

SAP ABAP 变量定义

SAP ABAP 字符串与常量

Abel's Coding Portal

Leetcode 344. Reverse String

HTML Overview

JavaScript Overview