力扣645. 错误的集合

2024-06-23 11:20

文章标签 力扣错误集合 645

本文主要是介绍力扣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 (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};}
}