在只讀數組中找到多個重複元素中的任何一個


難度級別
經常問 第一資本 Facebook 谷歌 確實 Microsoft微軟 Pinterest
排列 哈希

問題“查找只讀數組中的多個重複元素中的任何一個”狀態提示您被賦予了只讀狀態 排列 大小(n + 1)。 一個數組包含從1到n的整數。 您的任務是找出只讀數組中的任何重複元素。

在只讀數組中找到多個重複元素中的任何一個

n = 5
arr[] = [1,2,4,2,3,5]
2

解釋

這是只讀數組中唯一重複的元素。

n = 9
arr[] = [1,2,4,6,3,5,7,8,9,9]
9

解釋

這是只讀數組中唯一重複的元素。

算法

  1. 在你的生活中 “平方根” 到sqrt(n)。
  2. 將範圍設置為(n /平方根)+ 1。
  3. 創建一個大小範圍的數組。
  4. 以此計數並存儲每個元素的頻率(freqCount [(arr [i] – 1)/ squareroot] ++)。
  5. 在你的生活中 “ currentBlock” 到範圍1。
  6. 當我<range-1。
    1. 如果freqCount [i]> squareroot,則執行currentBlock = i併中斷。
  7. 聲明一個 地圖.
  8. 在地圖中遍歷以檢查屬於的元素 “ currentBlock”.
    1. 然後放入arr [i]並增加地圖鍵值的值。
    2. 如果發現鍵的值大於1,則返回arr [i]。
  9. 否則返回-1(未找到元素)。

解釋

我們已經提出了一個問題,以找出存在於所有整數從1到n且數組大小為n + 1的數組中的重複元素。 因為它顯示了一個重複元素的存在,所以它的大小為n + 1。

一個簡單的解決方案是創建一個HashMap並保留每個元素的頻率計數。 但是此解決方案需要O(N)時間和O(N)空間。 我們可以做得更好嗎?

我們可以使用類似於平方根分解的方法。 這種方法會將我們的空間複雜度降低到O(sqrt(N))。 我們創建一個大小為sqrt(N)+ 1的數組,並根據公式arr(i-1)/ sqrt(n)保持與值對應的索引的增量。 完成此操作後,我們肯定會找到一個頻率大於sqrt(N)的索引。 現在,我們將使用先前的方法,但僅用於屬於該範圍的元素。

哈希 解決該問題時使用了一些基本數學。 為了找出重複的元素,我們將傳遞一個數組,其值小於數組的大小1。 讓我們舉個例子來解決這個問題:

Array [] = {6,1,2,3,5,4,6},n = 6

如果大小是 n + 1 那我們就過去了 n 做到這一點。 現在我們必須找出 n 並將其存儲到一些變量說 平方根= 2。 現在我們必須找出數組的範圍。 我們將創建一個數組說 頻率計數 大小為'range = 4',我們可以找到(n / squareroot)+ 1的範圍。

我們將計算遍歷創建的數組範圍內每個元素的頻率。 每次遍歷時,我們都將遵循freCount [(arr(i)-1)/ squareroot] ++。

我們最終將在freqCount數組中具有以下值。

freqCount:[2,2,3,0]

設置 當前塊 到範圍-1(即3)。我們將遍歷 頻率計數 大批。 如果我們發現該值大於 平方根 在數組中。 我們發現在freqCount的第二個索引處,並將currentBlock設置為i併中斷。 我們將聲明一個 哈希圖 並遍歷輸入數組的每個元素,並檢查是否有任何元素屬於currentBlock和sqaureroot,如果是,則將其放在映射中並返回arr [i]的值。

我們的輸出將是:6

C ++代碼在只讀數組中查找多個重複元素中的任何一個

#include <unordered_map>
#include<iostream>
#include<math.h>
using namespace std;

int getRepeatedNumber(int arr[], int len)
{
    int squareroot = sqrt(len);
    int range = (len / squareroot) + 1;
    int count[range] = {0};

    for (int i = 0; i <= len; i++)
    {
        count[(arr[i] - 1) / squareroot]++;
    }
    int currentBlock = range - 1;
    for (int i = 0; i < range - 1; i++)
    {
        if (count[i] > squareroot)
        {
            currentBlock = i;
            break;
        }
    }
    unordered_map<int, int> m;
    for (int i = 0; i <= len; i++)
    {
        if ( ((currentBlock * squareroot) < arr[i]) && (arr[i] <= ((currentBlock + 1) * squareroot)))
        {
            m[arr[i]]++;
            if (m[arr[i]] > 1)
                return arr[i];
        }
    }
    return -1;
}
int main()
{
    int arr[] = { 6,1,2, 3, 5, 4, 6 };
    int n = 6;

    cout << "Repeated number(s) in the array is:"<< getRepeatedNumber(arr, n) << endl;
}
Repeated number(s) in the array is:6

Java代碼在只讀數組中查找多個重複元素中的任何一個

import java.util.*;
class arrayRepeatedElements
{
    public static int getRepeatedNumber(int[] arr, int len)
    {
        int squareroot = (int) Math.sqrt(len);
        int range = (len / squareroot) + 1;
        int freqCount[] = new int[range];
        for (int i = 0; i <= len; i++)
        {
            freqCount[(arr[i] - 1) / squareroot]++;
        }
        int currentBlock = range - 1;
        for (int i = 0; i < range - 1; i++)
        {
            if (freqCount[i] > squareroot)
            {
                currentBlock = i;
                break;
            }
        }
        HashMap<Integer, Integer> freq = new HashMap<>();
        for (int i = 0; i <= len; i++)
        {
            if ( ((currentBlock * squareroot ) < arr[i]) && ( arr[i] <= ((currentBlock + 1) * squareroot)))
            {
                freq.put(arr[i], 1);
                if (freq.get(arr[i])== 1)
                    return arr[i];
            }
        }
        return -1;
    }
    public static void main(String args[])
    {
        int[] arr = { 6,1, 2, 3, 5, 4, 6 };
        int n = 6;
        System.out.println("Repeated number(s) in the array is:"+getRepeatedNumber(arr, n));
    }
}
Repeated number(s) in the array is:6

複雜度分析

時間複雜度

上) 哪裡 “ N” 是(數組的長度– 1),即n –1。因為我們必須遍歷所有元素。

空間複雜度

平方根 哪裡 “ N” 是(數組的長度– 1),即n-1。 由於算法的性質。 首先,我們對等於sqrt(N)大小的部分進行計算。