一、題目大意
標簽: 陣列
https://leetcode.cn/problems/find-all-numbers-disappeared-in-an-array
給你一個含 n 個整數的陣列 nums ，其中 nums[i] 在區間 [1, n] 內，請你找出所有在 [1, n] 范圍內但沒有出現在 nums 中的數字，并以陣列的形式回傳結果，
示例 1：
輸入：nums = [4,3,2,7,8,2,3,1]
輸出：[5,6]
示例 2：
輸入：nums = [1,1]
輸出：[2]
提示：
- n == nums.length
- 1 <= n <= 105
- 1 <= nums[i] <= n
- 進階：你能在不使用額外空間且時間復雜度為 O(n) 的情況下解決這個問題嗎? 你可以假定回傳的陣列不算在額外空間內，
二、解題思路
把所有重復出現的位置進行標記，然后再遍歷一遍陣列，即可找到沒有出現過的數字，進一步優化，可以直接對原陣列進行標記：把重復出現的數字在原陣列出現的位置設為負數，最后仍然為正數的位置即為沒有出現過的數，
三、解題方法
3.1 Java實作
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
for (int num : nums) {
// 這個地方要注意 -1，陣列下標從0開始
int pos = Math.abs(num) - 1;
if (nums[pos] > 0) {
nums[pos] = -nums[pos];
}
}
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
ans.add(i + 1);
}
}
return ans;
}
}
四、總結小記
- 2022/8/3 下面做按資料結構開始做，先從陣列開始
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/500787.html
標籤：其他
上一篇：AtCoder Beginner Contest 262 題解
下一篇：第二講 軟體生命周期