包含重複項  


難度級別 容易獎學金
經常問 土磚 亞馬遜 蘋果
排列 哈希

我們得到了一個 排列 它可能包含重複元素,也可能不包含重複元素。 因此,我們需要檢查它是否包含重複項。

範例檔案  

包含重複項

[1, 3, 5, 1]
true
[“apple”, “mango”, “orange”, “mango”]
true
[22.0, 4.5, 3.98, 45.6, 13.54]
false

途徑  

我們可以通過幾種方式檢查數組,以檢查它是否包含重複項。 最常見的方法是“蠻力法”。 但是它的時間複雜度為O(n2),並且僅用於學術目的。 但是我們另一個人以更少的時間複雜性來解決我們的問題,即“哈希集方法”或“哈希表方法”,該方法比“蠻力方法”更有效。 哈希集方法採用O(n)的時間複雜度。

哈希設置方法

這種方法比其他方法更簡單,更有效。 我們需要知道的是該集合不包含重複項。 這意味著,如果我們嘗試添加設置的重複值,則會出現錯誤。 如果使用此方法,我們要做的就是循環遍歷數組元素,將其插入哈希集。 然後將集合的大小與數組進行比較。 如果不等於set,則數組包含重複項,否則不重複。

也可以看看
按頻率對元素進行排序

算法  

  1. 首先,我們創建一個將數組作為參數的函數。
  2. 之後,在我們的函數中,我們創建一個包含數組所有值的集合。
  3. Set不允許重複,這意味著如果數組包含重複項,則其大小將與集合的大小不同。
  4. 最後,我們比較數組和集合的大小。 如果它們的大小不同,則該數組包含重複項,否則所有元素都是不同的。

解釋

在我們的程序中,我們使用哈希集檢查重複項。首先,我們將創建一個檢查函數。 在其中我們將創建一個哈希集,並為其提供數組的所有值。 之後,該集合將刪除重複項(如果其中包含任何重複項),並且其大小與數組相比將有所不同,否則不會影響該集合的大小。

C ++代碼檢查數組是否包含重複項

#include <iostream>
#include <unordered_set>
using namespace std;

bool contain_duplicate(int arr[], int n)
{
    unordered_set<int> myset;
    bool flag = 0;

    for (int i = 0; i < n; i++)
    {
        if (myset.find(arr[i]) == myset.end())
            myset.insert(arr[i]);

        else
        {
            flag = 1;
            break;
        }

    }
    return flag;
}
int main()
{
    int arr[] = {1, 5, 2, 4, 3, 7, 8, 9, 1};
    int n = sizeof(arr) / sizeof(int);

    cout<< boolalpha <<contain_duplicate(arr, n);
    return 0;
}
true

Java代碼檢查數組是否包含重複項

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class contain_duplicate
{

    public static boolean solution(Integer [] array)
    {

        Set<Integer> myset = new HashSet<> (Arrays.asList(array));

        if(array.length!=myset.size())
        {
            return true;
        }
        else
        {
            return false;
        }
    }

    public static void main(String[] args)
    {
        Integer [] array = { 1, 2, 3, 6, 4, 9, 8, 1};
        System.out.println(solution(array));

    }
}
true

複雜度分析  

時間複雜度

O(n)其中“ n”是數組的大小。

也可以看看
最小路徑總和

空間複雜度

O(n)作為哈希表使用的空間與其中的元素數量成線性關係。