本文介绍: 再次遍历nums,如果遇到i位置上数nums[i]不大于n,则i+1并没有出现然后再次遍历nums发现只有在3位置上不大于4,所以3+1=4这个数未出现遍历nums,每遇到一个x,就让在x-1位置处的数+n。遇到2,在2-1=1位置上加4变成10。遇到1,在1-1=0位置上加4变成5。遇到2,在2-1=1位置上加4变成6。遇到3,在3-1=2位置上加4变成6。考虑nums数组本身当作哈希表。n = 4,下标从0开始。使用数组本身当作哈希表。

★448. 找到所有数组中消失的数字

使用数组本身当作哈希

考虑让nums数组本身当作哈希表。
遍历nums,每遇到一个x,就让在x-1位置处的数+n。
再次遍历nums,如果遇到i位置上数nums[i]不大于n,则i+1并没有出现

eg
n = 4,下标从0开始
1 2 2 3
⬇ ⬇ ⬇ ⬇
5 6 6 3

10

遇到1,在1-1=0位置上加4变成5
遇到2,在2-1=1位置上加4变成6
遇到2,在2-1=1位置上加4变成10
遇到3,在3-1=2位置上加4变成6

然后再次遍历nums发现只有在3位置上不大于4,所以3+1=4这个数未出现

class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        /**
            考虑让nums数组本身当作哈希表。
            遍历nums,每遇到一个数x,就让在x-1位置处的数+n。
            再次遍历nums,如果遇到i位置上数nums[i]不大于n,则i+1并没有出现。
        */
        List<Integer> list = new ArrayList();
        int n = nums.length;
        for(int i=0;i<nums.length;i++){
            int x = (nums[i] - 1) % n;  //可能多次
            nums[x] += n;
        }

        for(int i=0;i<nums.length;i++){
            if(nums[i] <= n)
                list.add(i+1);
        }
        return list;
    }
}

原文地址:https://blog.csdn.net/qq_45895217/article/details/134762957

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_34338.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注