LeetCode第三天(645. 错误的集合)

2024-03-25 07:52

本文主要是介绍LeetCode第三天(645. 错误的集合),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

集合 s 包含从 1 到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数,再找到丢失的整数,将它们以数组的形式返回。

我想的太简单了

class Solution {public int[] findErrorNums(int[] nums) {Arrays.sort(nums);for(int i = 0;i < nums.length-1;i++){if(nums[i] == nums[i+1]){nums[i+1] = nums[i] + 1;}}return nums;}
}

官解:

方法一:排序
将数组排序之后,比较每对相邻的元素,即可找到错误的集合。

寻找重复的数字较为简单,如果相邻的两个元素相等,则该元素为重复的数字。

寻找丢失的数字相对复杂,可能有以下两种情况:

如果丢失的数字大于 1 且小于 n,则一定存在相邻的两个元素的差等于 2,这两个元素之间的值即为丢失的数字;

如果丢失的数字是 1 或 n,则需要另外判断。

为了寻找丢失的数字,需要在遍历已排序数组的同时记录上一个元素,然后计算当前元素与上一个元素的差。考虑到丢失的数字可能是 1,因此需要将上一个元素初始化为 0。

当丢失的数字小于 n 时,通过计算当前元素与上一个元素的差,即可得到丢失的数字;

如果 nums[n−1]≠n,则丢失的数字是 n。

class Solution {public int[] findErrorNums(int[] nums) {int[] errorNums = new int[2];int n = nums.length;Arrays.sort(nums);int prev = 0;for (int i = 0; i < n; i++) {int curr = nums[i];if (curr == prev) {errorNums[0] = prev;} else if (curr - prev > 1) {errorNums[1] = prev + 1;}prev = curr;}if (nums[n - 1] != n) {errorNums[1] = n;}return errorNums;}
}

方法二:哈希表
重复的数字在数组中出现 2 次,丢失的数字在数组中出现 0 次,其余的每个数字在数组中出现 1 次。因此可以使用哈希表记录每个元素在数组中出现的次数,然后遍历从 1 到 n 的每个数字,分别找到出现 2 次和出现 0 次的数字,即为重复的数字和丢失的数字。

class Solution {public int[] findErrorNums(int[] nums) {int[] errorNums = new int[2];int n = nums.length;Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}for (int i = 1; i <= n; i++) {int count = map.getOrDefault(i, 0);if (count == 2) {errorNums[0] = i;} else if (count == 0) {errorNums[1] = i;}}return errorNums;}
}

 

 

 

这篇关于LeetCode第三天(645. 错误的集合)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/844325

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

uva 11178 计算集合模板题

题意: 求三角形行三个角三等分点射线交出的内三角形坐标。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

Java基础回顾系列-第三天-Lambda表达式

Java基础回顾系列-第三天-Lambda表达式 Lambda表达式方法引用引用静态方法引用实例化对象的方法引用特定类型的方法引用构造方法 内建函数式接口Function基础接口DoubleToIntFunction 类型转换接口Consumer消费型函数式接口Supplier供给型函数式接口Predicate断言型函数式接口 Stream API 该篇博文需重点了解:内建函数式

Java基础回顾系列-第六天-Java集合

Java基础回顾系列-第六天-Java集合 集合概述数组的弊端集合框架的优点Java集合关系图集合框架体系图java.util.Collection接口 List集合java.util.List接口java.util.ArrayListjava.util.LinkedListjava.util.Vector Set集合java.util.Set接口java.util.HashSetjava