要添加的元素,以便数组中存在某个范围的所有元素


难度级别 中等
经常问 GreyOrange 库利扎 Snapdeal 新思 Teradata数据 时代互联网
排列 哈希 哈希 排序

问题陈述

“要添加的元素以便范围内的所有元素都出现在数组中”指出给您一个整数数组。 问题陈述要求找出要添加到数组中的元素的数量,以便所有元素在数组中至少包含一次位于[X,Y]范围内(包括X和Y)。 X和Y分别是数组的最小和最大数。

使用案列

arr[] = {4,5,7,9,11}
3

说明:X和Y为4和11(分别为最小和最大数字),在这些数字的范围内,只有3个缺少6、8和10。

要添加的元素,以便数组中存在某个范围的所有元素

arr[] = {2,4,6,7}
2

说明:X和Y为2和7(分别为最小和最大数字),在这些数字的范围内,只有2个缺少3和5。

查找要添加的元素以便数组中存在所有元素的算法

1. Declare a Set.
2. Set output to 0, minValue to the maximum value of integer and maxValue to the minimum value of an integer.
3. Traverse the array and put all the values into the set and simultaneously find out the maximum and the minimum number of an array and store it to the maxValue and minValue respectively.
4. Traverse the array again, from minValue to maxValue.
5. Check if the map doesn’t contain any of the elements in traversal, then, increase the count of output.
6. Return output.

说明

我们有一个 整数 大批。 问题是找出要添加到数组中的元素的数量。 因此,所有元素都位于数组的最大和最小数目范围内,这样就不会出现任何元素至少出现一次。

声明一个Set,Set具有一个属性,该属性只能存储一次不同的元素。 这意味着它将删除公共元素,并仅存储不同的元素。 因此,我们将能够处理这种情况。 现在,我们将所有数组元素插入到集合中。 同时,我们将找出最大和最小元素。 这样我们就不必进行额外遍历即可找出最大值和最小值。 毕竟,我们只需要找出范围内缺失元素的数量即可。 因此,只需要对数字进行计数。 而且我们不必自己处理数字。

现在,我们将遍历数组,从数组中的最小值到数组的最大值。 因为这是我们需要的唯一范围。 我们将选择范围内的每个数字,并检查该集合是否不具有该范围的值。 如果该集合不包含该当前范围值,那么我们将增加输出计数。 每当我们在集合中不存在范围值时,每次将输出值增加1。 好像在上述代码中,最小值(4)和最大值(11)以及在(6,8)范围内缺少10和4,11之间一样,这些元素也不存在于数组中,因此将计算该元素的数量。 最后,我们将返回该输出。

代码

C ++代码查找要添加的元素,以便数组中存在某个范围的所有元素

#include<iostream>
#include<unordered_set>

using namespace std;

int getCountMissingNumber(int arr[], int n)
{
    unordered_set<int> SET;
    int output = 0;
    int maxValue = INT_MIN;
    int minValue = INT_MAX;

    for (int i = 0; i < n; i++)
    {
        SET.insert(arr[i]);
        if (arr[i] < minValue)
            minValue = arr[i];
        if (arr[i] > maxValue)
            maxValue = arr[i];
    }
    for (int a = minValue; a <= maxValue; a++)
    {
        if (SET.find(a) == SET.end())
        {
            output++;
        }
    }
    return output;
}
int main()
{
    int arr[] = {4,5,7,9,11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getCountMissingNumber(arr, n);
    return 0;
}
3

Java代码来查找要添加的元素,以便数组中存在某个范围的所有元素

import java.util.HashSet;

class NumberBwRange
{
    public static int getCountMissingNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<>();
        int output = 0;
        int maxValue = Integer.MIN_VALUE;
        int minValue = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
            if (arr[i] < minValue)
                minValue = arr[i];
            if (arr[i] > maxValue)
                maxValue = arr[i];
        }

        for (int i = minValue; i <= maxValue; i++)
            if (!SET.contains(i))
                output++;
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = { 4,5,7,9,11 };
        int n = arr.length;
        System.out.println(getCountMissingNumber(arr, n));
    }
}
3

复杂度分析

时间复杂度

O(最大-最小+ 1) 哪里 “最大” 以及 “最小” 最多 以及 最低限度 数组的值。 由于我们从最小元素遍历到最大元素。 这就是为什么在最坏的情况下该值可能会超过N个元素的原因。 因此,因为max-min + 1可能大于N。时间复杂度为O(max-min + 1),其中max表示最大元素,而min表示最小元素。

空间复杂度

上) 哪里 “N” 是数组中元素的数量。 由于我们仅存储N个元素,因此该算法具有线性空间复杂度。