( 数组和矩阵) 645. 错误的集合 ——【Leetcode每日一题】

这篇具有很好参考价值的文章主要介绍了( 数组和矩阵) 645. 错误的集合 ——【Leetcode每日一题】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

❓645. 错误的集合

难度:简单

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

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

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

示例 1:

输入:nums = [1,2,2,4]
输出:[2,3]

示例 2:

输入:nums = [1,1]
输出:[1,2]

提示:

  • 2 < = n u m s . l e n g t h < = 1 0 4 2 <= nums.length <= 10^4 2<=nums.length<=104
  • 1 < = n u m s [ i ] < = 1 0 4 1 <= nums[i] <= 10^4 1<=nums[i]<=104

💡思路:

法一:交换数组元素

最直接的方法是先对数组进行排序,这种方法时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。本题可以以 O ( n ) O(n) O(n) 的时间复杂度、 O ( 1 ) O(1) O(1) 空间复杂度来求解。

  • 主要思想是通过交换数组元素使得数组上的元素在正确的位置上
  • 这样只有 重复的数 出现在 丢失整数 的位置上。

法二:哈希表

重复的数字在数组中出现 2 次,丢失的数字在数组中出现 0次,其余的每个数字在数组中出现 1 次。因此可以使用哈希表记录每个元素在数组中是否出现

  • 如果出现两次,则找到了重复的数
  • 将所有数都存到哈希表,再遍历哈希表,则可找到丢失的数

🍁代码:(Java、C++)

法一:交换数组元素
Java

class Solution {
    public int[] findErrorNums(int[] nums) {
        for(int i = 0; i < nums.length; i++){
            while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){
                swap(nums, i, nums[i] - 1);
            }
        }
        for(int i = 1; i <= nums.length; i++){
            if(nums[i - 1] != i){
                return new int[]{nums[i - 1], i};
            }
        }
        return null;
    }
    private void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

C++

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]){
                swap(nums, i, nums[i] - 1);
            }
        }
        for(int i = 1; i <= nums.size(); i++){
            if(nums[i - 1] != i){
                return {nums[i - 1], i};
            }
        }
        return {};
    }
    void swap(vector<int>& nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
};

法二:哈希表
Java

class Solution {
    public int[] findErrorNums(int[] nums) {
        HashSet<Integer> s = new HashSet<>();
        int repeat = 0, lose = 0;
        for(int num : nums){
            if(s.contains(num)) repeat = num;
            s.add(num);
        }
        for(int i = 1; i <= nums.length; i++){
            if(!s.contains(i)){
                lose = i;
                break;
            }
        }
        return new int[]{repeat, lose};
    }
}

C++

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        unordered_set<int> s;
        int repeat = 0, lose = 0;
        for(int num : nums){
            if(s.find(num) != s.end()) repeat = num;
            s.insert(num);
        }
        for(int i = 1; i <= nums.size(); i++){
            if(s.find(i) == s.end()){
                lose = i;
                break;
            }
        }
        return {repeat, lose};
    }
};
🚀 运行结果:

( 数组和矩阵) 645. 错误的集合 ——【Leetcode每日一题】

🕔 复杂度分析:
  • 时间复杂度 O ( n ) O(n) O(n),其中 n 为数组的长度。
  • 空间复杂度 O ( 1 ) O(1) O(1),法一只需常量级空间;而哈希表需要创建大小为 O ( n ) O(n) O(n) 的哈希表,空间复杂度为 O ( n ) O(n) O(n)

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-440959.html

注: 如有不足,欢迎指正!

到了这里,关于( 数组和矩阵) 645. 错误的集合 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • (数组与矩阵) 剑指 Offer 03. 数组中重复的数字 ——【Leetcode每日一题】

    难度:简单 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 示例 1: 输入 : [2, 3, 1, 0, 2, 5, 3] 输出 :2 或

    2024年02月16日
    浏览(37)
  • ( 数组和矩阵) 485. 最大连续 1 的个数 ——【Leetcode每日一题】

    难度:简单 给定一个二进制数组 nums , 计算其中最大连续 1 的个数。 示例 1: 输入:nums = [1,1,0,1,1,1] 输出:3 解释:开头的两位和最后的三位都是连续 1 ,所以最大连续 1 的个数是 3. 示例 2: 输入:nums = [1,0,1,1,0,1] 输出:2 提示: 1 = n u m s . l e n g t h = 1 0 5 1 = nums.length = 10^5

    2024年02月08日
    浏览(43)
  • ( 数组和矩阵) 667. 优美的排列 II ——【Leetcode每日一题】

    难度:中等 给你两个整数 n 和 k ,请你构造一个答案列表 answer ,该列表应当包含从 1 到 n 的 n 个不同正整数,并同时满足下述条件: 假设该列表是 answer = [a1, a2, a3, ... , an] ,那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。 返回列表 answer

    2024年02月06日
    浏览(44)
  • ( 数组和矩阵) 378. 有序矩阵中第 K 小的元素 ——【Leetcode每日一题】

    难度:中等 给你一个 n x n n x n n x n 矩阵 m a t r i x matrix ma t r i x ,其中每行和每列元素均按升序排序,找到矩阵中第 k 小的元素。 请注意,它是 排序后 的第 k 小元素,而不是第 k 个 不同 的元素。 你必须找到一个内存复杂度优于 O ( n 2 ) O(n^2) O ( n 2 ) 的解决方案。 示例 1:

    2024年02月14日
    浏览(57)
  • (数组) 941. 有效的山脉数组 ——【Leetcode每日一题】

    难度:简单 给定一个整数数组 arr ,如果它是有效的山脉数组就返回 true ,否则返回 false 。 让我们回顾一下,如果 arr 满足下述条件,那么它是一个山脉数组: arr.length = 3 在 0 i arr.length - 1 条件下,存在 i 使得: arr[0] arr[1] ... arr[i-1] arr[i] arr[i] arr[i+1] ... arr[arr.length - 1] 示例

    2024年02月09日
    浏览(64)
  • LeetCode每日一题——1331.数组序号转换

    题目传送门 给你一个整数数组 arr ,请你将数组中的每个元素替换为它们排序后的序号。 序号代表了一个元素有多大。序号编号的规则如下: 序号从 1 开始编号。 一个元素越大,那么序号越大。如果两个元素相等,那么它们的序号相同。 每个数字的序号都应该尽可能地小。

    2024年02月14日
    浏览(36)
  • 【LeetCode每日一题】——1331.数组序号转换

    排序 简单 1331.数组序号转换 给你一个整数数组 arr ,请你将数组中的每个元素替换为它们排序后的序号。 序号代表了一个元素有多大。序号编号的规则如下: 序号从 1 开始编号。 一个元素越大,那么序号越大。如果两个元素相等,那么它们的序号相同。 每个数字的序号都

    2024年02月12日
    浏览(39)
  • Leetcode每日一题——“合并两个有序数组”

    各位CSDN的uu们你们好呀,又到小雅兰的愉快题解时候啦,今天,我们的题目内容是合并两个有序数组,下面,让我们进入合并两个有序数组的世界吧 示例 1: 输入:nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出:[1,2,2,3,5,6] 解释:需要合并 [1,2,3] 和 [2,5,6] 。 合并结果是 [ 1,2

    2023年04月24日
    浏览(64)
  • 645. 错误的集合

    645. 错误的集合

    2024年02月15日
    浏览(29)
  • ( 数组) 209. 长度最小的子数组——【Leetcode每日一题】

    难度:中等 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 示例 1: 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数

    2024年02月06日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包