配列内のK番目の異なる要素


難易度 ミディアム
よく聞かれる Adobe Amazon (アマゾン) Apple ByteDance オークション エクスペディア Facebook Google LinkedIn マイクロソフト オラクル Salesforce Spotifyは ウォルマート・ラボ
分割統治 ヒープ

あなたは整数を与えられます 配列 A、配列内のk番目の個別の要素を出力します。 指定された配列には重複が含まれている可能性があり、出力は配列内のすべての一意の要素の中でk番目に異なる要素を出力する必要があります。 kが複数の異なる要素である場合は、それを報告します。

入力:

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

K = 2

出力:

K番目の非反復要素は2です。

説明:

最初の非反復要素は1です。

2番目の非反復要素はXNUMXです。

アプローチ1:ブルートフォース

本旨

検出した非反復要素の数を格納するカウント変数を維持します。 ここで、すべての要素を反復処理し、各要素について、配列を反復処理して、これが非反復要素であるかどうかを確認します。非反復要素である場合は、カウントを1ずつインクリメントします。 Kに等しい場合、その要素を出力します。

配列内のK番目の異なる要素のアルゴリズム

  1. 変数カウントをゼロで初期化します。これにより、配列内の個別の要素の数がカウントされます。
  2. 0からn-1の範囲でIのループを実行します
    1. A [i]が繰り返し要素である場合、またはその逆の場合に真であるfalseでフラグを宣言します。
    2. 0からn-1の範囲でjのループを実行します
      1. Iがjに等しくなく、A [i]がA [j]に等しい場合は、flag = trueを割り当てて、ブレークします。
    3. フラグがfalseの場合、カウントを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のXNUMXつのネストされたループを使用しています。したがって、合計時間計算量は次のようになります。 O(N ^ 2).

スペースの複雑さ

余分なスペースを使用していないため、スペースの複雑さは O(1).

アプローチ2:ハッシュを使用する

本旨

配列の各要素の頻度をハッシュテーブルに格納します。 ここで、検出した非反復要素の数を格納するカウント変数を維持します。 次に、すべての要素を反復処理し、各要素について、その頻度が1より大きいかどうかを確認し、1に等しい場合は、カウントを1ずつ増やします。 Kに等しい場合、その要素を出力します。

配列内のK番目の異なる要素のアルゴリズム

  1. 配列の各要素の頻度を格納するハッシュテーブルを宣言します。
  2. 変数カウントをゼロで初期化します。これにより、配列内の個別の要素の数がカウントされます。
  3. 0からn-1の範囲でIのループを実行します
    1. A [i]の頻度が1の場合、カウントを1ずつ増やします。
    2. countが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番目の異なる要素の複雑さの分析

時間の複雑さ

配列をXNUMX回だけ繰り返しています。 したがって、合計時間計算量は オン).

スペースの複雑さ

配列内の要素の頻度を格納するためのハッシュテーブルを維持しています。 したがって、スペースの複雑さは オン).

リファレンス