本文主要是介绍力扣645. 错误的集合,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Problem: 645. 错误的集合
文章目录
- 题目描述
- 思路
- 复杂度
- Code
题目描述
思路
1.创建一个整数 n,表示数组 nums 的长度。创建一个整数 dup,初始化为 -1,用于存储重复的数字;
2.查找重复的数字:2.1.计算其绝对值减1后的索引 index。
2.2.如果 nums[index] 小于0,说明之前已经访问过该索引,对应的元素就是重复的,将其赋值给 dup。
2.3.如果 nums[index] 不小于0,说明这是第一次访问该索引,将 nums[index] 乘以 -1 标记为已访问。
3.查找缺失的数字:
3.1.创建一个整数 missing,初始化为 -1,用于存储缺失的数字。
3.2.再次遍历数组 nums,对于每个元素:如果 nums[i] 大于0,说明索引 i 对应的元素没有被标记,表示缺失的元素是 i + 1,将其赋值给 missing。
复杂度
时间复杂度:
O ( n ) O(n) O(n)
空间复杂度:
O ( 1 ) O(1) O(1)
Code
class Solution {/*** Find duplicates and missing numbers** @param nums Given array* @return int[]*/public int[] findErrorNums(int[] nums) {int n = nums.length;int dup = -1;for (int i = 0; i < n; ++i) {// The index should start at 0int index = Math.abs(nums[i]) - 1;if (nums[index] < 0) {dup = Math.abs(nums[i]);} else {nums[index] *= -1;}}int missing = -1;for (int i = 0; i < n; ++i) {if (nums[i] > 0) {// Convert the index to an elementmissing = i + 1;}}return new int[]{dup, missing};}
}
这篇关于力扣645. 错误的集合的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!