I. The main idea of the topic
tag: array
https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array
You are given an array nums of n integers, where nums[i] is in the interval [1, n].Please find all the numbers in the range [1, n] that do not appear in nums and return the result as an array.
Example 1:
Input: nums = [4,3,2,7,8,2,3,1]
Output: [5,6]
Example 2:
Input: nums = [1,1]
Output: [2]
Tip:
- n == nums.length
- 1 <= n <= 105
- 1 <= nums[i] <= n
- Advanced: Can you solve this problem without using extra space and in O(n) time complexity? You can assume that the returned array does not count in the extra space.
Second, problem-solving ideas
Mark all repeated occurrences, and then traverse the array again to find the numbers that have not appeared.For further optimization, the original array can be marked directly: the position where the repeated number appears in the original array is set to a negative number, and the position that is still positive at the end is the number that has not appeared before.
Three, problem solving methods
3.1 Java implementation
public class Solution {public List findDisappearedNumbers(int[] nums) {for (int num : nums) {// Pay attention to -1 here, the array subscript starts from 0int pos = Math.abs(num) - 1;if (nums[pos] > 0) {nums[pos] = -nums[pos];}}List ans = new ArrayList<>();for (int i = 0; i < nums.length; i++) {if (nums[i] > 0) {ans.add(i + 1);}}return ans;}} Four, Summary Notes
- 2022/8/3 Let's do the following according to the data structure, start with the array first
