大鹏一日同风起,扶摇直上九万里。这篇文章主要讲述leetCode-Find All Numbers Disappeared in an Array相关的知识,希望能为你提供帮助。
【leetCode-Find All Numbers Disappeared in an Array】Description:
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]
My Solution:
class Solution { public List< Integer> findDisappearedNumbers(int[] nums) { int len1 = nums.length; Set< Integer> set = new HashSet< Integer> (); Set< Integer> set1 = new HashSet< Integer> (); for(int i = 0; i < len1; i++){ set.add(Integer.valueOf(i + 1)); set1.add(Integer.valueOf(nums[i])); } set.removeAll(set1); return new ArrayList< Integer> (set); } }
Another Better Solution:
public class Solution {public List< Integer> findDisappearedNumbers(int[] nums) {List< Integer> list = new ArrayList< > (); boolean[] a = new boolean[nums.length + 1]; for(int i = 0; i < nums.length; i++) { a[nums[i]] = true; }for(int i = 1; i < a.length; i++) { if(!a[i]){ list.add(i); } }
return list; } }
总结:建立一个boolean数组,对应下标为true表示数值存在,false表示不存在,遍历nums,将nums值作为下标,赋为true。遍历boolean数组,为false值的下标即为不存在,添加到ArrayList即可(注意,boolean数组的长度为nums的长度加一,方便一一对应)。
重要的是要观察到nums值与即为boolean数组下标。
推荐阅读
- 11.21 异常详细信息: System.Data.SqlClient.SqlException:用户 'IIS APPPOOLDefaultAppPool' 登录失败解决办法(示例代
- Android java.lang.RuntimeException: Canvas: trying to use a recycled bitmap android.graphics.Bitmap@
- java----调用windows的DOS命令并回显/启动和关闭appium
- APP开发要理智
- android 上AES解密是报错javax.crypto.BadPaddingException: pad block corrupted
- Android视频编辑SDK--RDVECore来自锐动的无UI,高度抽象化API
- SpringMVC中的@Controller和@RequestMapping到底什么鬼()
- 互助推广APP免费解决自媒体推广难题
- Android LiveData简介