要添加的元素,以便數組中存在某個範圍的所有元素


難度級別
經常問 灰色橙色 庫利扎 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個元素,因此該算法具有線性空間複雜度。