首页 > itarticle > algorithm notes: leetcode#448 find all numbers disappeared in an array

algorithm notes: leetcode#448 find all numbers disappeared in an array

admin 11月 12, 2020 0

Problem

Solution 1

Analysis

Python implementation

1
2
3
4
5
6
7
 
class (object):
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        return list(set(range(1, len(nums)+1)) - set(nums))

Java implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
class  {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        Set<Integer> rangeSet = new HashSet<>();
        Set<Integer> numSet = new HashSet<>();
        
        for(int i = 1; i <= nums.length; i++)
            rangeSet.add(i);
        for(int num : nums)
            numSet.add(num);
            
        for(int n : rangeSet)
            if(!numSet.contains(n))
                ans.add(n);
        return ans;
    }
}

Time complexity

O(n).

Space complexity

O(n).

Solution 2

Analysis

Python implementation

1
2
3
4
5
6
7
8
9
10
 
class :
    def findDisappearedNumbers(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for n in nums:
            i = abs(n) - 1
            nums[i] = -abs(nums[i])
        return [i+1 for i, v in enumerate(nums) if v > 0]

Java implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
class  {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> ans = new ArrayList<>();
        
        for(int n : nums){
            int i = (n < 0 ? -n : n) - 1;
            nums[i] = nums[i] > 0 ? -nums[i] : nums[i];
        }
        
        for(int i = 0; i < nums.length; i++)
            if(nums[i] > 0)
                ans.add(i+1);
        return ans;
    }
}

Time compleixty

O(n).

Space complexity

O(1).

448. Find All Numbers Disappeared in an Array
(中文版) 算法笔记: 力扣#448 找到所有数组中消失的数字

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能