软件开发教程 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试
游戏开发 网络协议 系统运维 HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程
C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
 
   -> 数据结构与算法 -> c/c++ 力扣LeetCode 645.错误的集合 -> 正文阅读

[数据结构与算法]c/c++ 力扣LeetCode 645.错误的集合

题目链接

力扣 645.错误的集合

不想戳的看下图

解题思路

循环嵌套

对于这道题,有很多种方法。首先想到的,应是循环嵌套。直接for循环两边寻找相同,并求得丢失的整数。代码就不展示了,想必大家都会写。
但时间复杂度O(n2),是相当高的,对于这题的数据范围,不适合用这个方法。

map

我们想到,可以使用STL里面的map
代码如下:

class Solution {
    public int[] findErrorNums(int[] nums) {
    	int result[] = new int[2];
		Map<Integer, Integer> numMap = new HashMap<>();
		int len = nums.length;
		for (int i = 0; i < len; i++) {
            if (numMap.get(nums[i]) == null) {
                numMap.put(nums[i], 1);
            } else {
                numMap.put(nums[i], numMap.get(nums[i]) + 1);
            }
        }
		for (int key : numMap.keySet()) {
            int value = numMap.get(key);
            if (value == 2) {
                result[0] = key;
                break;
            }
        }
		for(int j =1;j<=len;j++){
            if(numMap.get(j)==null){
                result[1]=j;
            }
        }
		return result;
    }
}

哈希表

map是普通的计数法。我们在这里还有一种推荐:哈希表
首次遍历求出出错集合的和,二次遍历建立哈希表,找到重复的元素,之后两和相减求出加上出错元素的值

代码如下:

class Solution {
    public int[] findErrorNums(int[] nums) {
        int[] result = new int[2];
        int n=nums.length;
        int sum=n*(n+1)/2;
        int sum2=0;
        int x=-1;
        int[] temp = new int[nums.length+1];
        for(int i=0;i<nums.length;i++)
            sum2+=nums[i];
        for(int i=0;i<nums.length;i++)
        {
            if(temp[nums[i]]==0)
                temp[nums[i]]=1;
            else
            {
                x=nums[i];
                break;
            }
        }
        int cha=sum-sum2;
        result[0]=x;
        result[1]=x+cha;
        return result;
    }
}

小结

多刷题!

  数据结构与算法 最新文章
PTA (乙级)1035 插入与归并 (25 分)
动态规划学习
A. Find The Array
读《大话数据结构》记录Day 01
排序算法:希尔排序_代码
玩转算法(十二)——链表(删除链表)
西瓜书第四章拾遗
紫书第6章 数据结构基础 例题A~D
122 买卖股票的最佳时机-02
求二叉树最大深度
上一篇文章      下一篇文章      查看所有文章
加:2021-07-07 00:06:15  更:2021-07-07 00:07:10 
 
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年7日历 -2021/7/27 5:26:24-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件开发教程