leetcode448. Find All Numbers Disappeared in an Ar

blankyao 发布于2019-08-16 17:09 / 3270人阅读

摘要：题目要求假设一个长度为的整数数组，数组中的元素的值位于区间中。代码如下但是这个实现违背了的空间复杂度这里结果集不视为额外空间。如果当前元素无需进行交换，则指针右移一位。无需进行的场景是指当前元素已经出现在目标位置上了。

题目要求

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements of [1, n] inclusive that do not appear in this array.

Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[5,6]

假设一个长度为n的整数数组，数组中的元素的值位于[1,n]区间中。问，该数组中有哪些[1,n]区间中的整数没有出现？

思路和代码

首先可以想到用另一个临时数组来记录每个元素出现的次数，则出现次数为零次的元素在数组中没有出现。代码如下：

    public List findDisappearedNumbers(int[] nums) {
        int[] temp = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            temp[nums[i]]++;
        }
        
        List result = new ArrayList<>();
        for (int i = 1; i < temp.length; i++) {
            if (temp[i] == 0) {
                result.add(i);
            }
        }
        return result;
    }

但是这个实现违背了O(1)的空间复杂度（这里结果集不视为额外空间）。因此如何才能避免使用临时数组呢？其实我们可以利用原数组中元素相互调换的方式，将其转化为一个新的有序的数组。即从最左边开始，每遇到一个元素，就将其防止到元素的目标位置上，如在第0位上遇到元素i，则将位置i-1上的元素和位置0上的元素进行交换，并在此判断新的元素是否需要交换。如果当前元素无需进行交换，则指针右移一位。无需进行的场景是指当前元素已经出现在目标位置上了。

    public List findDisappearedNumbers(int[] nums) {
        int index = 0;
        while(index < nums.length) {
            if(nums[index] == nums[nums[index]-1]) {
                nums[nums[index]-1] = nums[index];
                index++;
            }else{
                int tmp = nums[index];
                nums[index] = nums[tmp-1];
                nums[tmp-1] = tmp;
            }
        }
        List result = new ArrayList();
        for(int i = 0 ; i < nums.length ; i++) {
            if(nums[i] != i+1) {
                result.add(i+1);
            }
        }
        return result;
    }

服务器托管私有云 FIND_IN_SET Disappeared Numbers Leetcod

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74414.html

leetcode 448 Find All Numbers Disappeared in an Ar

摘要：如果这个位置的值为正意味着我们还没有对这个元素进行过操作，我们将这个位置的元素的值取负。在整个遍历结束后，没有取负的值的索引，就可以对应到没有在数组出现过的值解法题目详情 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others ap...

MoAir 2019-08-15 13:54 评论0 收藏0
[LeetCode] 448. Find All Numbers Disappeared in an

Problem Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array...

X_AirDu 2019-08-16 14:28 评论0 收藏0
[LeetCode] 448. Find All Numbers Disappeared in an

Problem Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array...

Scorpion 2019-08-16 13:39 评论0 收藏0
448. Find All Numbers Disappeared in an Array

摘要：题目链接一般这种类型的题要，要么给赋值成不在范围内的数，要么到对应位置。 448. Find All Numbers Disappeared in an Array 题目链接：https://leetcode.com/problems... 一般这种类型的题要in place，要么给num[i]赋值成不在范围内的数，要么swap到对应位置。 public class Solution ...

DevWiki 2019-08-14 17:28 评论0 收藏0
Leetcode PHP题解--D79 448. Find All Numbers…

摘要：题目链接题目分析给定一个到的数组，返回其中缺失的数字。思路用得出到的数字，再用和给定的数组计算差集。最终代码若觉得本文章对你有用，欢迎用爱发电资助。 D79 448. Find All Numbers Disappeared in an Array 题目链接 448. Find All Numbers Disappeared in an Array 题目分析给定一个1到n的数组，返回...

X1nFLY 2019-07-01 13:57 评论0 收藏0