數組中的第K個不同元素


難度級別
經常問 土磚 亞馬遜 蘋果 ByteDance 易趣 Expedia的 Facebook 谷歌 LinkedIn Microsoft微軟 神諭 Salesforce的 Spotify 沃爾瑪實驗室
分而治之

給你一個整數 排列 A,在數組中打印第k個不同的元素。 給定的數組可能包含重複項,並且輸出應在數組的所有唯一元素中打印第k個不同的元素。 如果k大於多個不同的元素,則報告它。

輸入:

A [] = {3,4,4,1,2,3}

K = 2

輸出:

第K個非重複元素為2。

說明:

第一個非重複元素為1

第二個非重複元素是2。

方法1:蠻力

大意

我們將維護一個count變量,該變量將存儲我們發現的非重複元素的數量。 現在,我們將遍歷所有元素,對於每個元素,我們將遍歷數組以檢查這是否是一個非重複元素,如果是,則將計數加1。等於K,我們將打印該元素。

陣列中第K個不同元素的算法

  1. 用零初始化變量計數,該變量計數將計算數組中不同元素的數量。
  2. 對0到n-1的I進行循環
    1. 聲明一個帶有false的標誌,如果A [i]是一個重複元素,則為true,反之亦然
    2. 對j進行循環,範圍為0到n-1
      1. 如果I不等於j並且A [i]等於A [j],則分配flag = true併中斷
    3. 如果該標誌為假,則將計數遞增1
    4. 檢查計數是否等於K,則打印A [i]。
  3. 返回

履行

C ++程序

#include <bits/stdc++.h>
using namespace std;
void kthDistinctElement(vector<int> &A, int k)
{
    int n = A.size();
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        bool flag = false;
        for (int j = 0; j < n; j++)
        {
            if (i != j and A[i] == A[j])
            {
                flag = true;
                break;
            }
        }
        if (!flag)
        {
            count++;
        }
        if (count == k)
        {
            cout << "K-th non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "K is greater than number of distinct element in the array." << endl;
    return;
}
int main()
{
    vector<int> A = {3, 4, 4, 1, 2, 3};
    int k = 2;
    kthDistinctElement(A, k);
    return 0;
}
K-th non-repeating element is: 2

JAVA程序

public class Main
{
    static void kthDistinctElement(int A[], int k)
    {
        int n=A.length;
        int count = 0;
        for (int i = 0; i < n; i++)
        {
            boolean flag = false;
            for (int j = 0; j < n; j++)
            {
                if (i != j && A[i] == A[j])
                {
                    flag = true;
                    break;
                }
            }
            if (!flag)
            {
                count++;
            }
            if (count == k)
            {
                System.out.println("K-th non-repeating element is: " + A[i]);
                return;
            }
        }
        System.out.println("K is greater than number of distinct element in the array.");
    }
  public static void main(String[] args) {
    int A[] = {3, 4, 4, 1, 2, 3};
        int k = 2;
        kthDistinctElement(A, k);
  }
}
K-th non-repeating element is: 2

數組中第K個不同元素的複雜度分析

時間複雜度

我們正在使用兩個大小均為N的嵌套循環。因此,總的時間複雜度為 O(N ^ 2).

空間複雜度

我們沒有使用任何多餘的空間,所以空間複雜度是 O(1).

方法2:使用哈希

大意

我們將數組每個元素的頻率存儲在哈希表中。 現在,我們將維護一個count變量,該變量將存儲我們發現的非重複元素的數量。 接下來,我們將遍歷所有元素,對於每個元素,我們將檢查其頻率是否大於1,如果它等於1,則將計數增加1。等於K,我們將打印該元素。

陣列中第K個不同元素的算法

  1. 聲明一個哈希表,該表將存儲數組中每個元素的頻率。
  2. 用零初始化變量計數,該變量計數將計算數組中不同元素的數量。
  3. 對0到n-1的I進行循環
    1. 如果A [i]的頻率為1,則將計數加1。
    2. 如果計數等於K,則打印A [i]。
  4. 返回

例如:

A [] = {3,4,4,1,2,3}

K = 2

哈希表看起來像這樣,

數組中的第K個不同元素

履行

C ++程序

#include <bits/stdc++.h>
using namespace std;
void kthDistinctElement(vector<int> &A, int k)
{
    int n = A.size();
    int count = 0;
    unordered_map<int, int> hash_table;
    for (int i = 0; i < n; i++)
    {
        hash_table[A[i]]++;
    }
    for (int i = 0; i < n; i++)
    {
        if (hash_table[A[i]] == 1)
        {
            count++;
        }
        if (count == k)
        {
            cout << "K-th non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "K is greater than number of distinct element in the array." << endl;
    return;
}
int main()
{
    vector<int> A = {3, 4, 4, 1, 2, 3};
    int k = 2;
    kthDistinctElement(A, k);
    return 0;
}
K-th non-repeating element is: 2

JAVA程序

import java.util.*; 
public class Main
{
    static void kthDistinctElement(int A[], int k)
    {
        int n=A.length;
        int count = 0;
        HashMap <Integer, Integer> hash_table = new HashMap<Integer, Integer> ();  
        for (int i = 0; i < n; i++)  
        { 
            if(hash_table.containsKey(A[i])) 
                hash_table.put(A[i], hash_table.get(A[i]) + 1); 
            else
                hash_table.put(A[i], 1); 
        } 
        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                count++;
            }
            if (count == k)
            {
                System.out.println("K-th non-repeating element is: " + A[i]);
                return;
            }
        }
        System.out.println("K is greater than number of distinct element in the array.");
    }
  public static void main(String[] args) {
    int A[] = {3, 4, 4, 1, 2, 3};
        int k = 2;
        kthDistinctElement(A, k);
  }
}
K-th non-repeating element is: 2

數組中第K個不同元素的複雜度分析

時間複雜度

我們僅對數組進行兩次迭代。 因此,總時間複雜度為 上).

空間複雜度

我們正在維護一個哈希表,以存儲數組中元素的頻率。 因此,空間複雜度為 上).

參考