查找数组Leetcode解决方案中找不到的所有数字


难度级别 易得奖学金
经常问 土砖 亚马逊 Apple 彭博 谷歌 微软 雅虎
排列 哈希

问题陈述

在这个问题上,我们得到了一个 排列 整数它包含从1到N的元素,其中N =数组的大小。 但是,有些元素已消失,某些重复项存在。 我们的目标是返回所有这些消失的整数的数组。

使用案列

Array = {1 , 2 , 5 , 6 , 2 , 5}
3 4

查找数组Leetcode解决方案中找不到的所有数字

Array = {1 , 2 , 3 , 4}
n

查找数组Leetcode解决方案中找不到的所有数字

方法(使用HashSet)

我们可以标记数组中的每个元素,然后在以下范围内循环:[1,N],以检查数组中哪些元素丢失或丢失。 我们使用散列集来存储是否已标记整数。

算法

  1. 初始化哈希集 标记[整数] 存储存在的元素。
  2. 对于每个元素 i 在数组中:
    • 加入 i标记
  3. 初始化列表/向量 导致 将缺少的元素存储在数组中
  4. 对于每个元素 范围:[1,N]:
    • If 不存在 标记:
      • 将其添加到 导致
  5. 返回 导致
  6. 打印结果

数组Leetcode解决方案中消失的查找所有数字的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    unordered_set <int> mark;
    for(int &i : a)
        mark.insert(i);
    int N = a.size();
    vector <int> result;
    for(int i = 1 ; i <= N ; i++)
        if(mark.find(i) == mark.end())
            result.emplace_back(i);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

Java程序

import java.util.*;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        List <Integer> result = new ArrayList <Integer>();
        HashSet <Integer> mark = new HashSet <Integer>();
        for(int i : a)
            mark.add(i);

        for(int i = 1 ; i <= a.length ; i++)
            if(!mark.contains(i))
                result.add(i);

        return result;
    }
}
3 4

查找数组Leetcode解决方案中找不到的所有数字的复杂性分析

时间复杂度

上) 当我们遍历整个数组一次以标记整数时。 N =数组的大小。

空间复杂度 

上) 因为我们将数组中存在的所有数字存储在哈希表中。 注意,我们不考虑输出数组对空间复杂度的贡献。

方法(就地修改)

在此问题中需要注意的一点是:“数组始终包含小于或等于其大小的元素”。 这意味着索引与许多不同的元素一样多。 同样,丢失的元素将始终小于N(数组的大小)。 使用此约束,我们可以使用数组本身以某种方式存储整数的存在。 例如,假设我们可以写 真假 在元素的索引处分别表示其存在/不存在。 在我们的例子中,数组已经包含元素,因此这种存储/存储似乎不可行。 但是,由于我们知道所有元素都是正数,因此我们可以使用“负数”来表示是否在数组中看到了元素。 请注意,我们可以使用来获取存储在某个索引处的实际值 绝对() 该函数返回整数的绝对值。 这样,该数组既可以用作哈希映射,也可以用作容器。

例如,如果我们在数组中看到了元素“ 2”,则可以分配Array [1] = -1 * Array [1],这将告诉我们在数组中看到了元素2。

如果我们在索引处看到一个元素,此技巧将就地操作数组以进行存储 i。 完成后,我们可以在[1,N]范围内运行循环,以查找所有非负整数(表示尚未看到),从而打印所需的结果。 请注意,这只有在我们 允许 更改数组。

算法

  1. 对于每个元素 在数组中:
    • 如果Array [i – 1]> 0:
      • 将其设置为负数,或者Array [i – 1] * = -1;
  2. 初始化列表/向量 导致 存储所有缺少的元素
  3. 对于每个整数 在[1,N](N =数组大小)范围内:
    • If 数组[i]> 0
      • 添加这个元素 i导致
  4. 返回 导致
  5. 打印结果

数组Leetcode解决方案中消失的查找所有数字的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

vector <int> findDisappearedNumbers(vector <int> &a)
{
    int N = a.size();
    int idx;
    for(int i = 0 ; i < N ; i++)
    {
        idx = abs(a[i]) - 1;
        if(a[idx] > 0)
            a[idx] *= -1;
    }

    vector <int> result;
    for(int i = 0 ; i < N ; i++)
        if(a[i] > 0)
            result.emplace_back(i + 1);

    return result;
}

int main()
{
    vector <int> a = {1 , 2 , 5 , 6 , 2 , 5};
    vector <int> result = findDisappearedNumbers(a);
    if(result.empty())
        cout << "No disappeared elements\n";
    else
        for(int &i : result)
            cout << i << " ";
    return 0;
}

Java程序

import java.util.*;
import java.lang.Math;

class find_disappeared_numbers
{
    public static void main(String args[])
    {
        int[] a = {1 , 2 , 5 , 6 , 2 , 5};
        List <Integer> result = findDisappearedNumbers(a);
        if(result.size() == 0)
            System.out.println("No disappeared elements");
        else
            for(int i : result)
                System.out.print(i + " ");
    }

    static List <Integer> findDisappearedNumbers(int[] a)
    {
        int idx;
        for(int i = 0 ; i < a.length ; i++)
        {
            idx = Math.abs(a[i]) - 1;
            if(a[idx] > 0)
                a[idx] *= -1;
        }

        List <Integer> result = new ArrayList <Integer> ();

        for(int i = 0 ; i < a.length ; i++)
            if(a[i] > 0)
                result.add(i + 1);

        return result;
    }
}
3 4

查找数组Leetcode解决方案中找不到的所有数字的复杂性分析

时间复杂度

上) 当我们运行数组的两次遍历时,不管输入是什么,以查找丢失的元素。 N =数组的大小。

空间复杂度 

O(1) 因为我们使用恒定的内存空间。