ಮೊದಲ ಪುನರಾವರ್ತಿತ ಅಂಶ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಬೆಲ್ಜಬಾರ್ ಕೊಮ್ಲಿ ಮೀಡಿಯಾ ಮೆಟ್ಲೈಫ್ ಸ್ನ್ಯಾಪ್ಡಿಯಲ್ ಸ್ಪ್ರಿಂಕ್ಲರ್ ವೂಕರ್
ಅರೇ ಹ್ಯಾಶ್ ಹುಡುಕಲಾಗುತ್ತಿದೆ

ನಮಗೆ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗಿದೆ. ನಾವು ರಚನೆಯಲ್ಲಿ ಮೊದಲ ಪುನರಾವರ್ತಿಸದ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು.

ಉದಾಹರಣೆ

ಇನ್ಪುಟ್:

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

ಔಟ್ಪುಟ್:

ಪುನರಾವರ್ತಿಸದ ಮೊದಲ ಅಂಶವೆಂದರೆ: 3

ಏಕೆಂದರೆ 1, 2 ಉತ್ತರವಲ್ಲ ಏಕೆಂದರೆ ಅವು ಪುನರಾವರ್ತಿಸುತ್ತಿವೆ ಮತ್ತು 4 ಉತ್ತರವಲ್ಲ ಏಕೆಂದರೆ ನಾವು ಮೊದಲ ಪುನರಾವರ್ತಿಸದ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿದೆ, ಅದು 3, 4 ಅಲ್ಲ.

ಅಪ್ರೋಚ್ 1: ವಿವೇಚನಾರಹಿತ ಶಕ್ತಿ

ಮುಖ್ಯ ಉಪಾಯ

ನಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಅಂಶಕ್ಕೂ ಸರಣಿ, ನಾವು ಇಡೀ ಶ್ರೇಣಿಯನ್ನು ಪುನರಾವರ್ತಿಸುತ್ತೇವೆ ಮತ್ತು ಈ ಅಂಶವು ಪುನರಾವರ್ತನೆಯಾಗದಿದ್ದರೆ ನಾವು ಈ ಅಂಶವನ್ನು ಮುದ್ರಿಸುತ್ತೇವೆ.

ಕ್ರಮಾವಳಿ

  1. 0 ರಿಂದ n-1 ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ನನಗಾಗಿ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ
    1. 0 ರಿಂದ n ವ್ಯಾಪ್ತಿಯಲ್ಲಿ j ಗಾಗಿ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ
      1. J n ಗೆ ಸಮನಾಗಿದ್ದರೆ, A [i] ಅನ್ನು ಮುದ್ರಿಸಿ ಮತ್ತು ಹಿಂತಿರುಗಿ.
      2. ನಾನು j ಗೆ ಸಮನಾಗಿಲ್ಲದಿದ್ದರೆ ಮತ್ತು A [i] A [j] ಗೆ ಸಮನಾಗಿದ್ದರೆ, ಈ ಲೂಪ್‌ನಿಂದ ಮುರಿಯಿರಿ.
    2. ಎಲ್ಲಾ ಅಂಶಗಳು ರಚನೆಯಲ್ಲಿ ಪುನರಾವರ್ತಿಸುತ್ತಿವೆ ಎಂದು ಮುದ್ರಿಸಿ.

ಮೊದಲ ಪುನರಾವರ್ತಿಸದ ಅಂಶಕ್ಕಾಗಿ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (j == n)
            {
                cout << "First non-repeating element is: " << A[i] << endl;
                return;
            }
            if (j != i and A[i] == A[j])
            {
                break;
            }
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

ಜಾವಾ ಕಾರ್ಯಕ್ರಮ

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        int n = A.length;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                if (j == n)
                {
                    System.out.println("First non-repeating element is: "+A[i]);
                    return;
                }
                if (j != i && A[i] == A[j])
                {
                    break;
                }
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

ಮೊದಲ ಪುನರಾವರ್ತಿತ ಅಂಶಕ್ಕಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ನಮ್ಮಲ್ಲಿ N ಗಾತ್ರದ ಎರಡು ನೆಸ್ಟೆಡ್ ಲೂಪ್ಗಳಿವೆ, ಆದ್ದರಿಂದ ಒಟ್ಟು ಸಮಯದ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ ಒ (ಎನ್ ^ 2).

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ನಾವು ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಜಾಗವನ್ನು ಬಳಸುತ್ತಿಲ್ಲ ಆದ್ದರಿಂದ ಜಾಗದ ಸಂಕೀರ್ಣತೆ ಒ (1).

ಅಪ್ರೋಚ್ 2: ಹ್ಯಾಶಿಂಗ್ ಬಳಸುವುದು

ಮುಖ್ಯ ಉಪಾಯ

ನಾವು ಪ್ರತಿ ಅಂಶದ ಆವರ್ತನವನ್ನು ಹ್ಯಾಶ್ ಕೋಷ್ಟಕದಲ್ಲಿ ಸಂಗ್ರಹಿಸಬಹುದು ಮತ್ತು ಅದರ ನಂತರ ನಾವು ರಚನೆಯನ್ನು ಹಾದುಹೋಗಬಹುದು ಮತ್ತು ಆವರ್ತನ 1 ಆಗಿರುವ ಮೊದಲ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಬಹುದು.

ಕ್ರಮಾವಳಿ

  1. ಪ್ರತಿ ಅಂಶದ ಆವರ್ತನವನ್ನು ಹ್ಯಾಶ್ ಕೋಷ್ಟಕದಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ.
  2. 0 ರಿಂದ n-1 ವ್ಯಾಪ್ತಿಯಲ್ಲಿ ನನಗಾಗಿ ಲೂಪ್ ಅನ್ನು ಚಲಾಯಿಸಿ
    1. ಹ್ಯಾಶ್ ಕೋಷ್ಟಕದಲ್ಲಿ A [i] ನ ಆವರ್ತನ 1 ಆಗಿದ್ದರೆ, A [i] ಅನ್ನು ಮುದ್ರಿಸಿ ಮತ್ತು ಹಿಂತಿರುಗಿ.
  3. ಸರಣಿಯಲ್ಲಿನ ಎಲ್ಲಾ ಅಂಶಗಳು ಪುನರಾವರ್ತನೆಯಾಗುತ್ತವೆ ಎಂದು ಮುದ್ರಿಸಿ.

ಉದಾಹರಣೆಯೊಂದಿಗೆ ಅರ್ಥಮಾಡಿಕೊಳ್ಳಿ

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

ನಂತರ ಹ್ಯಾಶ್ ಟೇಬಲ್ ಈ ರೀತಿ ಕಾಣುತ್ತದೆ:

ಮೊದಲ ಪುನರಾವರ್ತಿತ ಅಂಶ

ಮೊದಲ ಪುನರಾವರ್ತಿಸದ ಅಂಶಕ್ಕಾಗಿ ಅನುಷ್ಠಾನ

ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <bits/stdc++.h>
using namespace std;
void firstNonRepeatingElement(vector<int> &A)
{
    int n = A.size();
    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)
        {
            cout << "First non-repeating element is: " << A[i] << endl;
            return;
        }
    }
    cout << "All the elements are repeating." << endl;
}
int main()
{
    vector<int> A = {2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
    return 0;
}
First non-repeating element is: 3

ಜಾವಾ ಕಾರ್ಯಕ್ರಮ

public class Main
{
    static void firstNonRepeatingElement(int A[])
    {
        java.util.HashMap<Integer, Integer> hash_table = new java.util.HashMap<Integer, Integer>();
        int n = A.length;
        for(int i=0;i<n;i++)
        {
            Integer freq = hash_table.get(A[i]);
            hash_table.put(A[i], (freq == null) ? 1 : freq + 1); 
        }

        for (int i = 0; i < n; i++)
        {
            if (hash_table.get(A[i])==1)
            {
                System.out.println("First non-repeating element is: "+A[i]);
                return;
            }
        }
        System.out.println("All the elements are repeating.");
    }
  public static void main(String[] args) {
    int A[]={2, 1, 2, 1, 3, 4};
    firstNonRepeatingElement(A);
  }
}
First non-repeating element is: 3

ಮೊದಲ ಪುನರಾವರ್ತಿತ ಅಂಶಕ್ಕಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ನಾವು ರಚನೆಯನ್ನು ಎರಡು ಬಾರಿ ಮಾತ್ರ ಪುನರಾವರ್ತಿಸುತ್ತಿದ್ದೇವೆ ಆದ್ದರಿಂದ ಒಟ್ಟು ಸಮಯದ ಸಂಕೀರ್ಣತೆಯಾಗಿದೆ ಒ (ಎನ್).

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ನಾವು ಹ್ಯಾಶ್ ಟೇಬಲ್ ಅನ್ನು ನಿರ್ವಹಿಸುತ್ತಿದ್ದೇವೆ ಆದ್ದರಿಂದ ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆ ಇರುತ್ತದೆ ಒ (ಎನ್).

ಉಲ್ಲೇಖಗಳು