一、题目
1、审题
2、分析
一个整形数组!元素值为 1~size; 出现的元素次数为 1~2 次。
求出所有 1~size 中没有出现的整数!
二、解答
1、思路
由于元素值都为 1~size之间。所以可以将数组下标 index 进行联系。
① 遍历数组,将出现的元素值对应的数组下标的元素都标记为负;
② 遍历数组,将下标对应的元素值为正的数组下标返回。因为此下标即为未出现的整数。
public List<Integer> findDisappearedNumbers(int[] nums) { ArrayList<Integer> result = new ArrayList<>(); // 将出现的数值对应的下标中的元素标记为负数 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) result.add(i + 1); } return result; }