LeetCode算法题-Find All Numbers Dis

这是悦乐书的第232次更新，第245篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第99题（顺位题号是448）。给定一个整数数组，其中1≤a[i]≤n（n =数组的大小），一些元素出现两次，其他元素出现一次。找到[1，n]包含的所有元素，这些元素不会出现在此数组中。你可以在没有额外空间和O（n）运行时的情况下完成吗？ 您可以假设返回的列表不计入额外空间。例如：

输入：[4,3,2,7,8,2,3,1]
输出：[5,6]

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

特殊情况：当数组中没有元素时，直接返回空list。

正常情况：先将数组排序，然后获取数组的第一个元素作为起始索引index，如果数组第一个元素不等于1，因为1≤a[i]≤n，所以需要先将前面缺的部分补起来。然后开始循环判断数组中的元素，如果index和当前元素相等，那么index自加1，循环内部的指针也加1；反之不相等，则需要判断当前元素和前一个元素是否相等，如果相等，循环内部的指针加1，否则就将index添加进list中，index再自加1。最后，还需要在判断一次，如果index小于数组的长度，则需要将后面缺的数也补起来。

此解法的时间复杂度是O(n log(n))，空间复杂度是O(1)。

public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> list = new ArrayList<Integer>();
    if (nums == null || nums.length < 1) {
        return list;
    }
    Arrays.sort(nums);
    int index = nums[0];
    if (index != 1) {
        for (int k=1; k<index; k++) {
            list.add(k);
        }
    }
    for (int i=0; i<nums.length; ) {
        if (index == nums[i]) {
            index++;
            i++;
        } else {
            if (nums[i] == nums[i-1]) {
                i++;
            } else {
                list.add(index++);
            }
        }
    }
    for (int j = index; j<=nums.length; j++) {
        list.add(j);
    }
    return list;
}

03 第二种解法

利用标记。因为1≤a[i]≤n，我们可以单独再新建一个数组，数组的长度是n+1，然后将nums中的元素作为索引，在新数组中对元素进行自加。然后判断新数组中，那些等于0的元素的索引就是nums中缺失的数。

public List<Integer> findDisappearedNumbers2(int[] nums) {
    List<Integer> list = new ArrayList<Integer>();
    if (nums == null || nums.length < 1) {
        return list;
    }
    int[] temp = new int[nums.length+1];
    for (int num : nums) {
        temp[num]++;
    }
    for (int i=1; i<temp.length; i++) {
        if (temp[i] == 0) {
            list.add(i);
        }
    }
    return list;
}

04 第三种解法

还是利用标记。在第二种解法中，我们使用了新数组，在此解法中，我们直接对nums进行标记。先遍历nums的元素，顺着索引，将其中的正数元素标记为负数。然后再去遍历数组，如果当前元素为正数，则说明其所在索引没有遇见过，就将其添加进list中。

public List<Integer> findDisappearedNumbers3(int[] nums) {
    List<Integer> list = new ArrayList<Integer>();
    if (nums == null || nums.length < 1) {
        return list;
    }
    for (int i = 0; i < nums.length; i++) {
        int val = Math.abs(nums[i]) - 1;
        if (nums[val] > 0) {
            nums[val] = -nums[val];
        }
    }
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] > 0) {
            list.add(i+1);
        }
    }
    return list;
}

05 小结

算法专题目前已日更超过三个月，算法题文章99+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！