448. Find All Numbers Disappeared in an Array

DevWiki 发布于2019-08-14 17:28 / 3221人阅读

摘要：题目链接一般这种类型的题要，要么给赋值成不在范围内的数，要么到对应位置。

448. Find All Numbers Disappeared in an Array

题目链接：https://leetcode.com/problems...

一般这种类型的题要in place，要么给num[i]赋值成不在范围内的数，要么swap到对应位置。

public class Solution {
    public List findDisappearedNumbers(int[] nums) {
        List result = new ArrayList();
        if(nums.length == 0) return result;
        // sign as negative when find a number
        for(int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            nums[index] = -Math.abs(nums[index]);
        }
        // find positive number, whose index is not visited
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) result.add(i + 1);
        }
        return result;
    }
}

swap的方法见discussion:
https://discuss.leetcode.com/...

public class Solution {
    public List findDisappearedNumbers(int[] nums) {
        List result = new ArrayList();
        if(nums.length == 0) return result;
        // swap to correct position
        for(int i = 0; i < nums.length; i++) {
            while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        // find positive number, whose index is not visited
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] != i + 1) result.add(i + 1);
        }
        return result;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

GPU云服务器云服务器 array_find FIND_IN_SET in_array() in_array

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

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

[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
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
leetcode448. Find All Numbers Disappeared in an Ar

摘要：题目要求假设一个长度为的整数数组，数组中的元素的值位于区间中。代码如下但是这个实现违背了的空间复杂度这里结果集不视为额外空间。如果当前元素无需进行交换，则指针右移一位。无需进行的场景是指当前元素已经出现在目标位置上了。题目要求 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some element...

blankyao 2019-08-16 17:09 评论0 收藏0
leedcode 数组：448. Find All Numbers Disappeared in a

摘要：题目描述思路先把数组进行升序排序，再进行数组去重，最后循环比较取得结果。升序排序可以使用若要降序排列可以则是数组去重，我使用的中的方法去重，可以参照一行代码实现数组去重数组去重数组去重方法最优解源码排序去重题目描述 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appe...

zero 2019-08-21 15:01 评论0 收藏0