LeetCode Find All Numbers Disappeared in an Array
原题链接在这里：https://leetcode.com/problems/find-all-numbers-disappeared-in-an-array/
题目：
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]
题解：
把nums[Math.abs(nums[i])-1]标负. 第二遍iterate 时若nums[i]非负，就表明原array没有i+1, 加到res中.
Time Complexity: O(nums.length). Space: O(1), regardless res.
AC Java:
public class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if(nums == null || nums.length == 0){
return res;
}
for(int i = 0; i<nums.length; i++){
int index = Math.abs(nums[i])-1;
if(nums[index] > 0){
nums[index] = -nums[index];
}
}
for(int i = 0; i<nums.length; i++){
if(nums[i] > 0){
res.add(i+1);
}
}
return res;
}
}
也可以把nums[i] swap到对应的index = nums[i]-1位置上.
第二遍iterate时，如果nums[i] != i+1. i+1就是disappeared, 加入res中.
Time Complexity: O(nums.length). Space: O(1), regardless res.
AC Java:
class Solution {
public List<Integer> findDisappearedNumbers(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
for(int i = 0; i<nums.length; i++){
if(nums[i]-1>=0 && nums[i]-1<nums.length && nums[i]!=nums[nums[i]-1]){
swap(nums, i, nums[i]-1);
i--;
}
}
for(int i = 0; i<nums.length; i++){
if(nums[i] != i+1){
res.add(i+1);
}
}
return res;
}
private void swap(int [] nums, int i, int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
跟上Find All Duplicates in an Array, Find the Duplicate Number, Missing Number.
最新文章
- Linux常用系统管理命令(top、free、kill、df)
- jq小插件--方便设置css属性
- 【Junit 报错】No appenders could be found for logger (org.springframework.core.env.StandardEnvironment).
- MySQL主主双机负载均衡
- mapreduce 自定义数据类型的简单的应用
- Struts2中的 配置文件
- [教程]Oracle 11g Express 安装和使用教程
- mongodb 修改数据结构的一个例子以及小梳理
- 【风马一族_xml】xml编程
- SVN菜单说明
- linux下利用openssl来实现证书的颁发（详细步骤）
- 【Android - 框架】之Fresco的使用
- MarkdownPad 使用 MathJax
- libMF阅读记录（一）：首先要编译通过
- servlet以及HTML中路径问题
- Servlet中请求重定向和请求转发和include
- Tomcat 请求处理流程详解
- Linux下的快速配置虚拟环境virtualenvwrapper
- python基础知识总结（二）
- JavaScript面向对象编程指南(五) 原型