ஒரு வரிசையில் K-th தனித்துவமான உறுப்பு  


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் ஆப்பிள் ByteDance ஈபே Expedia பேஸ்புக் கூகிள் லின்க்டு இன் மைக்ரோசாப்ட் ஆரக்கிள் விற்பனைக்குழு வீடிழந்து வால்மார்ட் ஆய்வகங்கள்
பிரித்து வெல்லுங்கள் குவியல்

உங்களுக்கு ஒரு முழு எண் கொடுக்கப்பட்டுள்ளது வரிசை A, ஒரு வரிசையில் k-th தனித்துவமான உறுப்பை அச்சிடுக. கொடுக்கப்பட்ட வரிசையில் நகல்கள் இருக்கலாம் மற்றும் வெளியீடு ஒரு வரிசையில் உள்ள அனைத்து தனித்துவமான கூறுகளுக்கிடையில் k-th தனித்துவமான உறுப்பை அச்சிட வேண்டும். K என்பது பல தனித்துவமான கூறுகளை விட அதிகமாக இருந்தால், அதைப் புகாரளிக்கவும்.

உதாரணமாக  

உள்ளீடு:

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

K = 2

வெளியீடு:

K-th மீண்டும் செய்யாத உறுப்பு 2 ஆகும்.

விளக்கம்:

முதல் மறுபயன்பாட்டு உறுப்பு 1,

இரண்டாவது மீண்டும் செய்யாத உறுப்பு 2 ஆகும்.

அணுகுமுறை 1: முரட்டு சக்தி  

முக்கிய யோசனை

நாம் கண்டறிந்த எண்ணிக்கையை மாற்றுவோம், அவை மீண்டும் மீண்டும் கூறப்படாத உறுப்புகளின் எண்ணிக்கையை சேமிக்கும். இப்போது நாம் எல்லா உறுப்புகளுக்கும் மேலாக மீண்டும் கூறுவோம், ஒவ்வொரு உறுப்புக்கும், இது மீண்டும் மீண்டும் செய்யப்படாத உறுப்பு இல்லையா என்பதை சரிபார்க்க வரிசைக்கு மேல் மீண்டும் கூறுவோம், அப்படியானால் எண்ணிக்கையை 1 ஆல் அதிகரிப்போம். K க்கு சமமாக, அந்த உறுப்பை அச்சிடுவோம்.

ஒரு வரிசையில் K-th தனித்துவமான உறுப்புக்கான வழிமுறை

  1. மாறி எண்ணிக்கையை பூஜ்ஜியத்துடன் தொடங்கவும், இது வரிசையில் உள்ள தனித்துவமான உறுப்புகளின் எண்ணிக்கையை எண்ணும்.
  2. 0 முதல் n-1 வரம்பில் எனக்கு ஒரு வளையத்தை இயக்கவும்
    1. ஒரு கொடியை பொய்யாக அறிவிக்கவும், இது A [i] மீண்டும் மீண்டும் வரும் உறுப்பு மற்றும் நேர்மாறாக இருந்தால் உண்மை
    2. 0 முதல் n-1 வரம்பில் j க்கு ஒரு சுழற்சியை இயக்கவும்
      1. நான் சமமான j மற்றும் A [i] A [j] க்கு சமமாக இல்லாவிட்டால், கொடி = உண்மை மற்றும் உடைக்க
    3. கொடி தவறானது என்றால், 1 இன் அதிகரிப்பு எண்ணிக்கை
    4. எண்ணிக்கை K க்கு சமமாக இருந்தால் சரிபார்க்கவும், A [i] ஐ அச்சிடவும்.
  3. திரும்ப
மேலும் காண்க
2 மாறிகள் பயன்படுத்தி ஃபைபோனச்சி வரிசையை அச்சிடுக

நடைமுறைப்படுத்தல்

சி ++ நிரல்

#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

ஒரு வரிசையில் K-th தனித்துவமான உறுப்புக்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

அளவு N இன் இரண்டு உள்ளமைந்த சுழல்களைப் பயன்படுத்துகிறோம். எனவே, மொத்த நேர சிக்கலானது ஓ (என் ^ 2).

விண்வெளி சிக்கலானது

நாங்கள் எந்த கூடுதல் இடத்தையும் பயன்படுத்தவில்லை, எனவே இட சிக்கலானது ஓ (1).

அணுகுமுறை 2: ஹாஷிங்கைப் பயன்படுத்துதல்  

முக்கிய யோசனை

வரிசையின் ஒவ்வொரு தனிமத்தின் அதிர்வெண்ணையும் ஒரு ஹாஷ் அட்டவணையில் சேமிப்போம். இப்போது நாம் கண்டறிந்த எண்ணிக்கையை மாற்றுவோம், இது நாம் கண்டறிந்த மீண்டும் மீண்டும் செய்யாத உறுப்புகளின் எண்ணிக்கையை சேமிக்கும். அடுத்து, எல்லா உறுப்புகளுக்கும் மேலாக மீண்டும் செயல்படுவோம், ஒவ்வொரு உறுப்புக்கும், அதன் அதிர்வெண் 1 ஐ விட அதிகமாக இருக்கிறதா இல்லையா என்பதைச் சோதிப்போம், அது 1 க்கு சமமாக இருந்தால், எண்ணிக்கையை 1 ஆல் அதிகரிப்போம். K க்கு சமமாக, அந்த உறுப்பை அச்சிடுவோம்.

மேலும் காண்க
வட்ட வரிசையைப் பயன்படுத்தி டெக் செயல்படுத்தல்

ஒரு வரிசையில் K-th தனித்துவமான உறுப்புக்கான வழிமுறை

  1. வரிசையின் ஒவ்வொரு உறுப்புகளின் அதிர்வெண்ணையும் சேமிக்கும் ஹாஷ் அட்டவணையை அறிவிக்கவும்.
  2. மாறி எண்ணிக்கையை பூஜ்ஜியத்துடன் தொடங்கவும், இது வரிசையில் உள்ள தனித்துவமான உறுப்புகளின் எண்ணிக்கையை எண்ணும்.
  3. 0 முதல் n-1 வரம்பில் எனக்கு ஒரு வளையத்தை இயக்கவும்
    1. A [i] இன் அதிர்வெண் 1 எனில், அதிகரிப்பு எண்ணிக்கை 1 ஆக இருக்கும்.
    2. எண்ணிக்கை K க்கு சமமாக இருந்தால், A [i] ஐ அச்சிடுக.
  4. திரும்ப

உதாரணமாக:

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

K = 2

ஹாஷ் அட்டவணை இப்படி இருக்கும்,

ஒரு வரிசையில் K-th தனித்துவமான உறுப்புமுள்

நடைமுறைப்படுத்தல்

சி ++ நிரல்

#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

ஒரு வரிசையில் K-th தனித்துவமான உறுப்புக்கான சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

நாங்கள் வரிசைக்கு இரண்டு முறை மட்டுமே மீண்டும் வருகிறோம். எனவே, மொத்த நேர சிக்கலானது ஓ (என்).

மேலும் காண்க
படிக்க மட்டும் வரிசையில் பல மீண்டும் மீண்டும் கூறுகளில் ஏதேனும் ஒன்றைக் கண்டறியவும்

விண்வெளி சிக்கலானது

வரிசையில் உள்ள உறுப்புகளின் அதிர்வெண்ணை சேமிக்க ஒரு ஹாஷ் அட்டவணையை நாங்கள் பராமரிக்கிறோம். எனவே, விண்வெளி சிக்கலானது ஓ (என்).

குறிப்புகள்