Leetcode

Find All Numbers Disappeared in an Array

  • Time:O(n)
  • Space:O(1)

C++

class Solution {
 public:
  vector<int> findDisappearedNumbers(vector<int>& nums) {
    vector<int> ans;

    for (const int num : nums) {
      const int index = abs(num) - 1;
      nums[index] = -abs(nums[index]);
    }

    for (int i = 0; i < nums.size(); ++i)
      if (nums[i] > 0)
        ans.push_back(i + 1);

    return ans;
  }
};

JAVA

class Solution {
  public List<Integer> findDisappearedNumbers(int[] nums) {
    List<Integer> ans = new ArrayList<>();

    for (final int num : nums) {
      final int index = Math.abs(num) - 1;
      nums[index] = -Math.abs(nums[index]);
    }

    for (int i = 0; i < nums.length; ++i)
      if (nums[i] > 0)
        ans.add(i + 1);

    return ans;
  }
}

Python

class Solution:
  def findDisappearedNumbers(self, nums: List[int]) -> List[int]:
    for num in nums:
      index = abs(num) - 1
      nums[index] = -abs(nums[index])

    return [i + 1 for i, num in enumerate(nums) if num > 0]