Find All Numbers Disappeared in an Array-K6K4.com

原题： https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/description/

题意： 给定一个整数数组，其中1 ≤ a[i] ≤ n (n = 数组长度)，一些元素出现两次，其他的出现一次。寻找所有[1, n]中没有出现在数组中的元素。

约定： 不使用额外空间并在O(n)运行时间求解，可以假设返回列表不算额外空间

例子：

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

标签： disappeared、numbers、find、额外、array、面试

猜你感兴趣的圈子：

LeetCode交流圈

星空

2017-08-18 16:48:32 1楼#1层

class Solution {
     public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> ret = new ArrayList<Integer>();
        
        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) {
                ret.add(i+1);
            }
        }
        return ret;
    }
}

星空

2017-08-18 16:48:56 2楼#1层

class Solution(object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for n in nums:
            nums[abs(n) - 1] = -abs(nums[abs(n) - 1])
        return [i + 1 for i, n in enumerate(nums) if n > 0]

星空

2017-08-18 16:50:21 3楼#1层

class Solution {
     public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < nums.length; i ++) nums[(nums[i]-1) % n] += n;
        for (int i = 0; i < nums.length; i ++) if (nums[i] <= n) res.add(i+1);
        return res;
    }
}

取消

回复

推荐圈子

LeetCode交流圈