内容简介:假设一个长度为n的整数数组,数组中的元素的值位于[1,n]区间中。问,该数组中有哪些[1,n]区间中的整数没有出现?首先可以想到用另一个临时数组来记录每个元素出现的次数,则出现次数为零次的元素在数组中没有出现。代码如下:但是这个实现违背了O(1)的空间复杂度(这里结果集不视为额外空间)。因此如何才能避免使用临时数组呢?其实我们可以利用原数组中元素相互调换的方式,将其转化为一个新的有序的数组。即从最左边开始,每遇到一个元素,就将其防止到元素的目标位置上,如在第0位上遇到元素i,则将位置i-1上的元素和位置0上
题目要求
Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space. Example: Input: [4,3,2,7,8,2,3,1] Output: [5,6]
假设一个长度为n的整数数组,数组中的元素的值位于[1,n]区间中。问,该数组中有哪些[1,n]区间中的整数没有出现?
思路和代码
首先可以想到用另一个临时数组来记录每个元素出现的次数,则出现次数为零次的元素在数组中没有出现。代码如下:
public List<Integer> findDisappearedNumbers(int[] nums) { int[] temp = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { temp[nums[i]]++; } List<Integer> result = new ArrayList<>(); for (int i = 1; i < temp.length; i++) { if (temp[i] == 0) { result.add(i); } } return result; }
但是这个实现违背了O(1)的空间复杂度(这里结果集不视为额外空间)。因此如何才能避免使用临时数组呢?其实我们可以利用原数组中元素相互调换的方式,将其转化为一个新的有序的数组。即从最左边开始,每遇到一个元素,就将其防止到元素的目标位置上,如在第0位上遇到元素i,则将位置i-1上的元素和位置0上的元素进行交换,并在此判断新的元素是否需要交换。如果当前元素无需进行交换,则指针右移一位。无需进行的场景是指当前元素已经出现在目标位置上了。
public List<Integer> findDisappearedNumbers(int[] nums) { int index = 0; while(index < nums.length) { if(nums[index] == nums[nums[index]-1]) { nums[nums[index]-1] = nums[index]; index++; }else{ int tmp = nums[index]; nums[index] = nums[tmp-1]; nums[tmp-1] = tmp; } } List<Integer> result = new ArrayList<Integer>(); for(int i = 0 ; i < nums.length ; i++) { if(nums[i] != i+1) { result.add(i+1); } } return result; }
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:- leetcode448. Find All Numbers Disappeared in an Array
- Leetcode PHP题解--D79 448. Find All Numbers Disappeared in an Array
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
现代前端技术解析
张成文 / 电子工业出版社 / 2017-4-1 / 79.00元
这是一本以现代前端技术思想与理论为主要内容的书。前端技术发展迅速,涉及的技术点很多,我们往往需要阅读很多书籍才能理解前端技术的知识体系。《现代前端技术解析》在前端知识体系上做了很好的总结和梳理,涵盖了现代前端技术绝大部分的知识内容,起到一个启蒙作用,能帮助读者快速把握前端技术的整个脉络,培养更完善的体系化思维,掌握更多灵活的前端代码架构方法,使读者获得成为高级前端工程师或架构师所必须具备的思维和能......一起来看看 《现代前端技术解析》 这本书的介绍吧!