ອົງປະກອບທີ່ບໍ່ຊ້ ຳ ອີກຄັ້ງ ທຳ ອິດ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ ເບລາຊາບາ ສື່ມວນຊົນ Komli MetLife Snapdeal ສະເປສີດ Wooker
Array Hash ຊອກຫາ

ພວກເຮົາໄດ້ຮັບການຈັດລຽງແຖວ A. ພວກເຮົາຕ້ອງຊອກຫາອົງປະກອບ ທຳ ອິດທີ່ບໍ່ເຮັດຊ້ ຳ ໃນອາເລ.

ຍົກຕົວຢ່າງ  

ການປ້ອນຂໍ້ມູນ:

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

ຜົນໄດ້ຮັບ:

ສ່ວນປະກອບທີ່ບໍ່ເຮັດຊ້ ຳ ອີກຄັ້ງ ທຳ ອິດແມ່ນ: 3

ເພາະວ່າຂໍ້ທີ 1, 2 ບໍ່ແມ່ນ ຄຳ ຕອບເພາະວ່າພວກເຂົາ ກຳ ລັງເຮັດຊ້ ຳ ແລະ 4 ບໍ່ແມ່ນ ຄຳ ຕອບເພາະພວກເຮົາຕ້ອງຊອກຫາອົງປະກອບທີ່ບໍ່ ທຳ ອິດ, ເຊິ່ງແມ່ນ 3, ບໍ່ແມ່ນ 4.

ວິທີການທີ 1: ກຳ ລັງແຮງ  

ຄວາມ​ຄິດ​ຫຼັກ

ສຳ ລັບທຸກໆອົງປະກອບໃນ array, ພວກເຮົາຈະປັບປຸງອາຄານທັງ ໝົດ ແລະຖ້າອົງປະກອບນີ້ບໍ່ຊ້ ຳ ອີກແລ້ວພວກເຮົາພຽງແຕ່ຈະພິມອົງປະກອບນີ້.

ລະບົບວິເຄາະ

  1. ດໍາເນີນການ loop ສໍາລັບ I ໃນລະດັບ 0 ເຖິງ n-1
    1. ດໍາເນີນການ loop ສໍາລັບ j ໃນລະດັບ 0 ເຖິງ n
      1. ຖ້າ j ກາຍເປັນເທົ່າກັບ n, ຫຼັງຈາກນັ້ນພິມ A [i] ແລ້ວກັບຄືນ.
      2. ຖ້າຂ້ອຍບໍ່ເທົ່າກັບ j ແລະ A [i] ເທົ່າກັບ A [j], ແລ້ວແຍກຈາກ loop ນີ້.
    2. ພິມວ່າທຸກໆອົງປະກອບ ກຳ ລັງເຮັດຊ້ ຳ ໃນຂບວນ.

ການຈັດຕັ້ງປະຕິບັດ ສຳ ລັບ Element ທີ່ບໍ່ຊ້ ຳ ຊ້ອນຄັ້ງ ທຳ ອິດ

ໂຄງການ C ++

#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

ໂຄງການ JAVA

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, ສະນັ້ນຄວາມສັບສົນທັງ ໝົດ ຂອງເວລາແມ່ນ O (N ^ 2).

ເບິ່ງ
Vowels ປະຕິເສດຂອງ String Leetcode Solution

ຄວາມສັບສົນໃນອະວະກາດ

ພວກເຮົາບໍ່ໄດ້ໃຊ້ພື້ນທີ່ພິເສດຫຍັງເລີຍສະນັ້ນຄວາມສັບສົນຂອງພື້ນທີ່ກໍ່ຄືກັນ O (1).

ວິທີທີ່ 2: ການ ນຳ ໃຊ້ hashing  

ຄວາມ​ຄິດ​ຫຼັກ

ພວກເຮົາສາມາດເກັບຮັກສາຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບໃນຕາຕະລາງ hash ແລະຫລັງຈາກນັ້ນພວກເຮົາສາມາດຂ້າມອາເລແລະພົບອົງປະກອບ ທຳ ອິດທີ່ຄວາມຖີ່ຂອງມັນແມ່ນ 1.

ລະບົບວິເຄາະ

  1. ເກັບຮັກສາຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບໃນຕາຕະລາງ hash.
  2. ດໍາເນີນການ loop ສໍາລັບ I ໃນລະດັບ 0 ເຖິງ n-1
    1. ຖ້າຄວາມຖີ່ຂອງ A [i] ໃນຕາຕະລາງ hash ແມ່ນ 1, ພິມ A [i] ແລະກັບຄືນ.
  3. ພິມວ່າມີສ່ວນປະກອບທັງ ໝົດ ໃນແຖວທີ່ ກຳ ລັງເຮັດຊ້ ຳ ອີກ.

ເຂົ້າໃຈກັບຕົວຢ່າງ

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

ຫຼັງຈາກນັ້ນ, ຕາຕະລາງ hash ຈະມີລັກສະນະດັ່ງນີ້:

ອົງປະກອບທີ່ບໍ່ຊ້ ຳ ອີກຄັ້ງ ທຳ ອິດPin

ການຈັດຕັ້ງປະຕິບັດ ສຳ ລັບ Element ທີ່ບໍ່ຊ້ ຳ ຊ້ອນຄັ້ງ ທຳ ອິດ

ໂຄງການ C ++

#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

ໂຄງການ JAVA

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

ການວິເຄາະຄວາມສັບສົນ ສຳ ລັບອົງປະກອບທີ່ບໍ່ຊ້ ຳ ອີກຄັ້ງ ທຳ ອິດ

ຄວາມສັບສົນເວລາ

ພວກເຮົາ ກຳ ລັງປັບປ່ຽນອາຄານພຽງແຕ່ສອງເທົ່າເທົ່ານັ້ນສະນັ້ນຄວາມສັບສົນຂອງເວລາທັງ ໝົດ ແມ່ນ ໂອ (N).

ເບິ່ງ
ຜົນລວມຂອງອົງປະກອບຕ່ ຳ ແລະສູງສຸດຂອງ subarrays ທັງ ໝົດ ຂອງຂະ ໜາດ k

ຄວາມສັບສົນໃນອະວະກາດ

ພວກເຮົາ ກຳ ລັງຮັກສາຕາຕະລາງ hash ດັ່ງນັ້ນຄວາມສັບສົນຂອງພື້ນທີ່ແມ່ນ ໂອ (N).

ເອກະສານ