數組中存在的最大連續數  


難度級別 容易獎學金
經常問 ol石 土磚 亞馬遜 風箏 空氣質量
排列 哈希

問題陳述  

假設您有一個數組 整數 大小為N。問題“數組中存在最大連續數”要求找出可能分散在數組中的連續數的最大計數。

例  

arr[] = {2, 24, 30, 26, 99, 25}
3

說明: 連續的數字是⇒24、25、26(一組3個)。

arr[] = { -8, 9 , -1, -6, -5}
2

說明: 連續的數字為⇒-6,-5(一組2)。

算法  

1. Declare a set.
2. Do traversing of the array, and insert all the values of array into the Set.
3. Set output to 0.
4. Traverse the array from i=0, to i<n(length of the array).
  1. Check if Set contains the arr[i].
    1. If true, then pick the current array element and store it to temp.
  2. While Set contains the temp, repeatedly increases the values of temp.
  3. Find out the maximum between output and temp-arr[i] and store it into the output.
5. Return output.

解釋  

給定一個 整數 排列,我們必須找出數組中存在的最大連續數字。 我們將使用 Wi-Fi:。 Set提供了刪除相似元素的功能。 因此,我們不必擔心handle公用元素,它將被自動處理。

也可以看看
打印給定整數數組的所有不同元素

我們將把數組的所有值添加到Set中。 因為稍後,我們還將檢查連續的數字。 我們將再次遍歷數組,選擇每個元素並檢查是否 地圖 擁有arr [i],如果為true,那麼我們將將該元素放入一個臨時變量中,並再次檢查映射是否包含該溫度;如果為true,則將temp的值增加1,然後再次進行檢查,然後再次增加它,繼續進行直到地圖沒有該增加的值為止。 現在,當我們退出此循環時,將獲得映射中當前數組元素的增量最大的值,並將其增加1的計數,因此它也將是連續的數字。

現在,我們必須找出輸出的最大值和temp-arr [i]的差,不要認為該差給出的計數值有誤,因為我們會從中獲得temp的增量值。循環,我們將獲得正確的連續數字計數。 然後,我們將存儲輸出和temp-arr [i](輸出,temp-arr [i])之差之間的最大值。 Arr [i]只是一系列連續數字和溫度的起點。 遍歷整個數組之後,將重複這些步驟,直到找到最大輸出為止。

數組中存在的最大連續數

履行  

C ++程序查找數組中存在的最大連續數

#include<iostream>
#include<unordered_set>

using namespace std;

int getMaxConsecutiveNumber(int arr[], int n)
{
    unordered_set<int> SET;
    for (int i = 0; i < n; i++)
        SET.insert(arr[i]);

    int output = 0;
    for (int i = 0; i < n; i++)
    {
        if (SET.find(arr[i] - 1) == SET.end())
        {
            int temp = arr[i];

            while (SET.find(temp) != SET.end())
                temp++;

            output = max(output, temp - arr[i]);
        }
    }
    return output;
}
int main()
{
    int arr[] = {2, 24, 30, 26, 99, 25 };
    int n = sizeof(arr) / sizeof(int);
    cout << "Largest Set found : "<<getMaxConsecutiveNumber(arr, n)<< endl;
    return 0;
}
Largest Set found : 3

Java程序查找數組中存在的最大連續數

import java.util.HashSet;

class LargestConsecutiveSet
{
    public static int getMaxConsecutiveNumber(int arr[], int n)
    {
        HashSet<Integer> SET = new HashSet<Integer>();
        for (int i = 0; i < n; i++)
        {
            SET.add(arr[i]);
        }
        int output = 0;
        for (int i = 0; i < n; i++)
        {
            if(SET.contains(arr[i]))
            {
                int temp = arr[i];
                while (SET.contains(temp))
                    temp ++;

                output = Math.max(output, temp - arr[i]);
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {2, 24, 30, 26, 99, 25};
        int n = arr.length;
        System.out.println("Largest Set found : "+getMaxConsecutiveNumber(arr, n));
    }
}
Largest Set found : 3

複雜性分析以查找數組中存在的最大連續數  

時間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 因為我們使用了HashSet,它允許在固定時間內進行插入,刪除和搜索操作。

也可以看看
將兩個連續的相等值替換為一個更大的值

空間複雜度

O(N) 哪裡 “ n” 是數組中元素的數量。 我們在集合中存儲了N個元素,因此線性空間複雜度。

參考文獻