LeetCode 算法题 - Set Mismatch(Java 实现)

这是悦乐书的第 279 次更新, 第 295 篇原创

01 看题和准备

今天介绍的是 LeetCode 算法题中 Easy 级别的第 147 题(顺位题号是 645). 集合 S 最初包含从 1 到 n 的数字. 但不幸的是, 由于数据错误, 集合中的一个数字被复制到集合中的另一个数字, 这导致重复一个数字而丢失另一个数字. 给定一个数组 nums, 表示错误后该集的数据状态. 要求先找到两次出现的数字, 然后找到丢失的数数字, 最后以数组的形式返回它们. 例如:

输入: nums = [1,2,2,4]

输出:[2,3]

注意:

给定的数组大小将在 [2,10000] 范围内.

给定数组的数字无序.

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

02 第一种解法

题目的意思是根据给出的数组, 找出两个数, 第一个数是该数组中重复出现的那个数, 第二个数是该数组中缺失的那个数, 也就是说最后返回的结果数组, 两个数是有先后顺序的.

先对数组排序, 然后从第二位开始遍历数组, 如果当前一位与前一位相等, 说明重复了, 那么第一位数就找到了. 如果当前元素比前一位元素加 1 后还要大, 说明前一位元素是重复出现的那个数的第二个, 也就是要找的缺失的那个数.

但是, 还有两种特殊情况需要考虑, 因为题目并不能保证数组首尾不缺少元素. 第一, nums 的第一位是不是从 1 开始? 如果不是, 那么第二个数就是 1. 第二, nums 的最后一位元素是不是和数组长度相等? 如果不相等, 那么第二个数就是数组的长度.

此解法的时间复杂度是 O(nlog(n)), 空间复杂度是 O(1).

public int[] findErrorNums(int[] nums) {
    // 排序
    Arrays.sort(nums);
    int[] result = new int[2];
    for (int i=1; i<nums.length; i++) {
        if (nums[i] == nums[i-1]) {
            // 第一个数, 重复出现的元素
            result[0] = nums[i];
        } else if (nums[i]> nums[i-1]+1) {
            // 第二个数, 缺失的那个数
            result[1] = nums[i-1]+1;
        }
    }
    // 数组第一个元素不是 1
    if (nums[0] != 1) {
        result[1] = 1;
    } else if (nums[nums.length-1] != nums.length) {
        // 数组最后一个元素不是数组的长度
        result[1] = nums.length;
    }
    return result;
}

03 第二种解法

我们也可以不排序, 使用 HashMap. 先将数组的元素都添加进 map 中, 以元素值为 key, 出现次数为 value. 然后开始循环, 从 0 到数组的长度, 如果 map 中包含当前索引值加 1, 并且它出现的次数为 2 次, 那么第一个数就是该元素, 否则第二个元素就是当前缺失的索引值加 1.

此解法的时间复杂度是 O(n), 最坏情况是 O(n^2), 空间复杂度是 O(n).

public int[] findErrorNums(int[] nums) {
    int[] result = new int[2];
    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int num : nums) {
        map.put(num, map.getOrDefault(num, 0)+1);
    }
    for (int i=0; i<nums.length; i++) {
        if (map.containsKey(i+1)) {
            // 出现两次的重复元素
            if (map.get(i+1) == 2) {
                result[0] = i+1;
            }
        } else {
            // 缺失的元素
            result[1] = i+1;
        }
    }
    return result;
}

04 第三种解法

我们也可以不使用 HashMap, 使用数组进行代替. 思路与第二种解法类似.

此解法的时间复杂度是 O(n), 空间复杂度是 O(n).

public int[] findErrorNums(int[] nums) {
    int[] result = new int[2];
    // 新建一个数组, 长度比 nums 大 1
    int[] arr = new int[nums.length+1];
    for (int i=0; i<nums.length; i++) {
        // 以 nums 的元素作为索引, 出现次数为 value
        arr[nums[i]]++;
    }
    // 数组的元素值是从 1 开始的, 所以新数组也从第二位开始遍历
    for (int i=1; i<arr.length; i++) {
        // 重复出现的元素
        if (arr[i] == 2) {
            result[0] = i;
        } else if (arr[i] == 0) {
            // 缺失的元素
            result[1] = i;
        }
    }
    return result;
}

05 第四种解法

我们还可以使用减法. 先将数组元素正常情况下的元素之和算出来, 因为是从 1 到 n 的数, 是一个公差为 1 的等差数列, 可以直接套用等差数列求和的公式来计算和, 然后用算出来的和减去数组中的每一个元素, 最后和可能是正 1, 也可能是负 1, 因为数组中有重复元素, 也就可能多 1 或者少 1, 也即是重复项元素值多 1 或者少 1, 所以缺失的那个数可以直接使用最后的和与重复项元素相加得到.

此解法的时间复杂度是 O(n), 空间复杂度是 O(n).

public int[] findErrorNums(int[] nums) {
    int[] result = new int[2];
    // 定义一个 HashSet
    Set<Integer> set = new HashSet<Integer>();
    // 等差数列求和公式
    long sum = nums.length*(nums.length+1)/2;
    for (int i=0; i<nums.length; i++) {
        // 重复出现的那个数
        if (set.contains(nums[i])) {
            result[0] = nums[i];
        }
        set.add(nums[i]);
        // 减去每一个元素
        sum -= nums[i];
    }
    // sum 最后可能是正数, 也可能是负数, 与重复元素相加后, 正好是缺失的那个数
    result[1] = (int)sum + result[0];
    return result;
}

06 第五种解法

我们可以对原数组进行标记, 将元素变成负数, 如果遇到的元素是小于 0 的, 说明已经对该元素变过一次负数, 也就是说该元素重复了, 最后在遍历一次数组, 如果遇到大于 0 的数, 表明在该位置缺少一个元素.

此解法的时间复杂度是 O(n), 空间复杂度是 O(1).

public int[] findErrorNums(int[] nums) {
    int[] result = new int[2];
    for (int num : nums) {
        if (nums[Math.abs(num)-1] <0) {
            // 已经转过一次负数的数, 表明重复
            result[0] = Math.abs(num);
        } else {
            // 将所有元素转为负数
            nums[Math.abs(num)-1] *= -1;
        }
    }
    for (int i=1; i<nums.length; i++) {
        // 剩下那个没有被转成负数的数
        if (nums[i]> 0) {
            result[1] = i+1;
        }
    }
    return result;
}

07 第六种解法

此解法是使用异或运算, 来自讨论区. 传送门:

public int[] findErrorNums(int[] nums) {
    int[] ans = new int[2];
    for(int i = 0; i < nums.length; i++) {
        int val = Math.abs(nums[i]);
        ans[1] ^= (i+1) ^ val;
        if (nums[val-1] < 0) ans[0] = val;
        else nums[val-1] = -nums[val-1];
    }
    ans[1] ^= ans[0];
    return ans;
}

08 小结

算法专题目前已日更超过四个月, 算法题文章 147 + 篇, 公众号对话框回复[数据结构与算法] ,[算法] ,[数据结构] 中的任一关键词, 获取系列文章合集.

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

来源: http://www.jianshu.com/p/781262143d26