LeetCode-----算法448.找到所有数组中消失的数字
2024-09-06 00:56:15
题目:
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。
找到所有在 [1, n] 范围之间没有出现在数组中的数字。
您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
示例:
输入:
[,,,,,,,] 输出:
[,]
<分析>
1. 1 ≤ a[i] ≤ n ( n = 数组大小 )
2. 数组中的元素一些出现了两次,另一些只出现一次
解法一:
可以考虑将数组a中的出现的元素k放到数组a第k个位置,即a[k-1]单元.。 如此,数组a中下标+1(i+1)与元素a[i]不相等则代表i+1未出现过。
函数如下:
public static List<Integer> findDisappearedNumbers(int[] nums) {
int i, k;
List<Integer> L = new ArrayList<>(); for(i = 0; i < nums.length; i++){
if(nums[i] != nums[nums[i] - 1]){
k = nums[i];
nums[i] = nums[k - 1];
nums[k - 1] = k;
i--;
}
}
for(i = 0; i < nums.length; i++){
if(i != nums[i] - 1)
L.add(i+1);
} return L;
}
解法二:
1-n的数字可能出现也可能不出现,可以想一种方法标记两种状态。数组中元素均大于0,考虑如果数组a[]中包含k,则可以将a[k-1]取-|a[k-1]|。这样遍历完数组a[]后,a[i]>0,则代表i+1未出现。
函数如下:
public static List<Integer> findDisappearedNumbers(int[] nums) {
int i, k;
List<Integer> L = new ArrayList<>(); for(i = 0; i < nums.length; i++){
k = nums[i] > 0 ? nums[i] : -nums[i];
nums[k - 1] = nums[k - 1] > 0 ? -nums[k - 1] : nums[k - 1]; } for(i = 0; i < nums.length; i++){
if(nums[i] > 0)
L.add(i+1);
} return L;
}
解法三:
与解法二类似,可以采用其他方式标记。若k在数组a[]中出现,可以让a[k-1]加上n。这样,如果a[i]<=n则代表i+1未出现。
代码如下:
public static List<Integer> findDisappearedNumbers(int[] nums) {
int i, k;
List<Integer> L = new ArrayList<>(); for(i = 0; i < nums.length; i++){
k = nums[i] % nums.length;
if(k == 0)
k = nums.length;
nums[k - 1] += nums.length;
} for(i = 0; i < nums.length; i++){
if(nums[i] <= nums.length)
L.add(i+1);
} return L;
}
最新文章
- [转]HttpModule的认识
- TSql 巧用Alt 键
- Leetcode Reverse Nodes in k-Group
- How to Programmatically Switch between the HubTile Visual States
- 给伪类设置z-index= -1;
- Android Studio插件
- (转载)VC/MFC 工具栏上动态添加组合框等控件的方法
- 有什么很好的软件是用 Qt 编写的?
- appium 真机测试问题 出现 instruments crashed on startup
- 修改Oracle【12C】字符集
- 浅谈,html\css脱离标准文档流相关
- c++(循环单向链表)
- JAVA如何request没有参数的post提交
- ssh-免密登录批量发送脚本
- GIT TEAMWORK
- axios请求本地json
- Oracle使用ODBC连接配置
- linux一键修改mysql密码脚本
- BZOJ:2460[BeiJing2011]元素 (异或基+贪心)
- django-model之Q查询补充
热门文章
- 关于Vue的nextTick的一点小理解
- 布局:上下两个div高度固定,中间自适应
- cenos6.5 python2.6.6升级至python2.7.3
- Android SDK4/5/6/7,相册、拍照及裁剪功能及遇见的坑
- js 按指定属性给对象数组排序(json数组)
- Jquery属性练习
- #define GPIOA ((GPIO_TypeDef *) GPIOA_BASE)
- 快速在Ubuntu安装PHP网站
- python 字典,元组,对象,数组取值方法
- C3P0配置实战