ഒരു നിരയിലെ കെ-ത്ത് വ്യത്യസ്ത ഘടകം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു അഡോബി ആമസോൺ ആപ്പിൾ ബൈറ്റ്ഡാൻസ് ബെ ബൈ ഫേസ്ബുക്ക് ഗൂഗിൾ ലിങ്ക്ഡ് മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ Salesforce നീനുവിനും വാൾമാർട്ട് ലാബുകൾ
ഭിന്നിപ്പിച്ചു കീഴടക്കുക കൂമ്പാരം

നിങ്ങൾക്ക് ഒരു പൂർണ്ണസംഖ്യ നൽകിയിരിക്കുന്നു ശ്രേണി A, ഒരു ശ്രേണിയിൽ k-th വ്യതിരിക്തമായ ഘടകം അച്ചടിക്കുക. തന്നിരിക്കുന്ന അറേയിൽ‌ തനിപ്പകർ‌പ്പുകൾ‌ അടങ്ങിയിരിക്കാം കൂടാതെ a ട്ട്‌പുട്ടിൽ‌ ഒരു അറേയിലെ എല്ലാ അദ്വിതീയ ഘടകങ്ങൾ‌ക്കിടയിലും k-th വ്യതിരിക്തമായ ഘടകം അച്ചടിക്കണം. K നിരവധി വ്യത്യസ്ത ഘടകങ്ങളേക്കാൾ കൂടുതലാണെങ്കിൽ, അത് റിപ്പോർട്ടുചെയ്യുക.

ഉദാഹരണം

ഇൻപുട്ട്:

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

കെ = 2

ഔട്ട്പുട്ട്:

K-th ആവർത്തിക്കാത്ത ഘടകം 2 ആണ്.

വിശദീകരണം:

ആദ്യത്തെ ആവർത്തിക്കാത്ത ഘടകം 1,

ആവർത്തിക്കാത്ത രണ്ടാമത്തെ ഘടകം 2 ആണ്.

സമീപനം 1: മൃഗീയമായ ശക്തി

പ്രധാന ആശയം

ഞങ്ങൾ കണ്ടെത്തിയ ഒരു ആവർത്തിക്കാത്ത ഘടകങ്ങളുടെ എണ്ണം സംഭരിക്കുന്ന ഒരു എണ്ണം വേരിയബിൾ ഞങ്ങൾ നിലനിർത്തും. ഇപ്പോൾ ഞങ്ങൾ എല്ലാ ഘടകങ്ങൾക്കും മുകളിലൂടെ ആവർത്തിക്കും, ഓരോ ഘടകത്തിനും, ഇത് ആവർത്തിക്കാത്ത ഘടകമാണോ അല്ലയോ എന്ന് പരിശോധിക്കാൻ ഞങ്ങൾ അറേയിലൂടെ ആവർത്തിക്കും, അങ്ങനെയാണെങ്കിൽ ഞങ്ങൾ എണ്ണം 1 വർദ്ധിപ്പിക്കും. K ന് തുല്യമായി, ഞങ്ങൾ ആ ഘടകം പ്രിന്റുചെയ്യും.

ഒരു അറേയിലെ കെ-ത്ത് ഡിസ്റ്റിംഗ്റ്റ് എലമെന്റിനുള്ള അൽഗോരിതം

  1. പൂജ്യത്തോടുകൂടിയ ഒരു വേരിയബിൾ എണ്ണം സമാരംഭിക്കുക, അത് അറേയിലെ വ്യത്യസ്ത ഘടകങ്ങളുടെ എണ്ണം കണക്കാക്കും.
  2. 0 മുതൽ n-1 വരെയുള്ള ശ്രേണിയിൽ എനിക്കായി ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക
    1. A [i] ആവർത്തിക്കുന്ന ഘടകമാണെങ്കിൽ തിരിച്ചും ശരിയാണെന്നും ഒരു ഫ്ലാഗ് തെറ്റായി പ്രഖ്യാപിക്കുക
    2. 0 മുതൽ n-1 വരെയുള്ള ശ്രേണിയിൽ j നായി ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക
      1. ഞാൻ തുല്യമല്ല j ഉം A [i] A [j] ന് തുല്യവുമാണെങ്കിൽ, ഫ്ലാഗ് = true എന്ന് നൽകി ബ്രേക്ക് ചെയ്യുക
    3. ഫ്ലാഗ് തെറ്റാണെങ്കിൽ, വർദ്ധനവ് എണ്ണം 1 വർദ്ധിപ്പിക്കുക
    4. എണ്ണം K ന് തുല്യമാണോയെന്ന് പരിശോധിക്കുക, A [i] പ്രിന്റുചെയ്യുക.
  3. മടങ്ങുക

നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

ജാവ പ്രോഗ്രാം

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

ഒരു അറേയിലെ കെ-ത്ത് ഡിസ്റ്റിംഗ്റ്റ് എലമെന്റിനായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

വലുപ്പം N ന്റെ രണ്ട് നെസ്റ്റഡ് ലൂപ്പുകളാണ് ഞങ്ങൾ ഉപയോഗിക്കുന്നത്. അതിനാൽ, മൊത്തം സമയ സങ്കീർണ്ണതയാണ് O (N ^ 2).

സ്ഥല സങ്കീർണ്ണത

ഞങ്ങൾ അധിക സ്ഥലമൊന്നും ഉപയോഗിക്കുന്നില്ല, അതിനാൽ സ്ഥല സങ്കീർണ്ണതയാണ് O (1).

സമീപനം 2: ഹാഷിംഗ് ഉപയോഗിക്കുന്നു

പ്രധാന ആശയം

അറേയുടെ ഓരോ ഘടകത്തിന്റെയും ആവൃത്തി ഞങ്ങൾ ഒരു ഹാഷ് പട്ടികയിൽ സംഭരിക്കും. ഇപ്പോൾ ഞങ്ങൾ ഒരു എണ്ണം വേരിയബിൾ നിലനിർത്തും, അത് ഞങ്ങൾ കണ്ടെത്തിയ ആവർത്തിക്കാത്ത ഘടകങ്ങളുടെ എണ്ണം സംഭരിക്കും. അടുത്തതായി, ഞങ്ങൾ എല്ലാ ഘടകങ്ങളെക്കാളും ആവർത്തനം ചെയ്യും, ഓരോ ഘടകത്തിനും, അതിന്റെ ആവൃത്തി 1 നേക്കാൾ വലുതാണോ അല്ലയോ എന്ന് പരിശോധിക്കും, അത് 1 ന് തുല്യമാണെങ്കിൽ, ഞങ്ങൾ എണ്ണം 1 വർദ്ധിപ്പിക്കും. K ന് തുല്യമായി, ഞങ്ങൾ ആ ഘടകം പ്രിന്റുചെയ്യും.

ഒരു അറേയിലെ കെ-ത്ത് ഡിസ്റ്റിംഗ്റ്റ് എലമെന്റിനുള്ള അൽഗോരിതം

  1. അറേയിലെ ഓരോ ഘടകത്തിന്റെയും ആവൃത്തി സംഭരിക്കുന്ന ഒരു ഹാഷ് പട്ടിക പ്രഖ്യാപിക്കുക.
  2. പൂജ്യത്തോടുകൂടിയ ഒരു വേരിയബിൾ എണ്ണം സമാരംഭിക്കുക, അത് അറേയിലെ വ്യത്യസ്ത ഘടകങ്ങളുടെ എണ്ണം കണക്കാക്കും.
  3. 0 മുതൽ n-1 വരെയുള്ള ശ്രേണിയിൽ എനിക്കായി ഒരു ലൂപ്പ് പ്രവർത്തിപ്പിക്കുക
    1. A [i] ന്റെ ആവൃത്തി 1 ആണെങ്കിൽ, വർദ്ധനവ് എണ്ണം 1.
    2. എണ്ണം K ന് തുല്യമാണെങ്കിൽ, A [i] പ്രിന്റുചെയ്യുക.
  4. മടങ്ങുക

ഉദാഹരണത്തിന്:

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

കെ = 2

ഹാഷ് പട്ടിക ഇതുപോലെ കാണപ്പെടും,

ഒരു നിരയിലെ കെ-ത്ത് വ്യത്യസ്ത ഘടകം

നടപ്പിലാക്കൽ

സി ++ പ്രോഗ്രാം

#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

ജാവ പ്രോഗ്രാം

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

ഒരു അറേയിലെ കെ-ത്ത് ഡിസ്റ്റിംഗ്റ്റ് എലമെന്റിനായുള്ള സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

ഞങ്ങൾ അറേയിൽ രണ്ടുതവണ മാത്രം ആവർത്തിക്കുന്നു. അതിനാൽ, മൊത്തം സമയ സങ്കീർണ്ണതയാണ് O (N).

സ്ഥല സങ്കീർണ്ണത

അറേയിലെ ഘടകങ്ങളുടെ ആവൃത്തി സംഭരിക്കുന്നതിന് ഞങ്ങൾ ഒരു ഹാഷ് പട്ടിക പരിപാലിക്കുന്നു. അതിനാൽ, സ്ഥല സങ്കീർണ്ണതയാണ് O (N).

അവലംബം