ອົງປະກອບ ທຳ ອິດເກີດຂື້ນ k ເທື່ອໃນແຖວ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon hike PayU ຫ້ອງທົດລອງ SAP Teradata Wipro Yatra Zoho
Array Hash

ພວກເຮົາໄດ້ໃຫ້ ໝາຍ ເລກ 'k' ແລະຕົວເລກເລກເຕັມ. ບັນຫາ“ ອົງປະກອບ ທຳ ອິດທີ່ເກີດຂື້ນ k ເທື່ອໃນອາເລ” ກ່າວວ່າເພື່ອຊອກຫາອົງປະກອບ ທຳ ອິດໃນແຖວທີ່ເກີດຂື້ນແນ່ນອນ k ເທື່ອໃນຂບວນ. ຖ້າບໍ່ມີສ່ວນປະກອບໃນອາເລທີ່ເກີດຂື້ນ k ເວລາ k ກັບຄືນມາ -1.

ຍົກຕົວຢ່າງ

ຊອກຫາອົງປະກອບທີ່ຂາດຫາຍໄປຂອງຊ່ວງໃດ ໜຶ່ງ

Arr[]={1,4,5,2,4,2,7},  k=2
4

ຄໍາອະທິບາຍ

ໃນຕົວຢ່າງນີ້, ມັນມີສອງອົງປະກອບທີ່ເກີດຂື້ນ k ເວລາ. 4 ແລະ 2 ມີຈໍານວນ k ຂອງເວລາແນ່ນອນ, ແຕ່ 4 ແມ່ນຄັ້ງທໍາອິດທີ່ເກີດຂື້ນ k ເວລາ. ສະນັ້ນພວກເຮົາກັບຄືນມາ 4.

ລະບົບວິເຄາະ

  1. ປະກາດກ HashMap.
  2. ຂ້າມອາເລ.
    • ນັບແລະເກັບຄວາມຖີ່ຂອງແຕ່ລະສ່ວນປະກອບຂອງອາເລເຂົ້າໃນແຜນທີ່.
  3. ອີກເທື່ອ ໜຶ່ງ ເຮັດຕາມອາເລແລະກວດເບິ່ງວ່າຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບຂອງອາເລເທົ່າກັບ k.
    • ຖ້າສະພາບການພໍໃຈ, ຫຼັງຈາກນັ້ນໃຫ້ກັບຄືນອົງປະກອບ.

ຄໍາອະທິບາຍ

ພວກເຮົາມີຄຸນຄ່າການປ້ອນຂໍ້ມູນຂອງພວກເຮົາຄືກັນ integer array ແລະເລກເຕັມ k. ຄຳ ຖະແຫຼງກ່ຽວກັບບັນຫາຮຽກຮ້ອງໃຫ້ຊອກຫາອົງປະກອບ ທຳ ອິດໃນແຖວທີ່ເກີດຂື້ນແນ່ນອນ k ເທື່ອ. ເພື່ອແກ້ໄຂບັນຫານີ້, ພວກເຮົາຈະ ນຳ ໃຊ້ ແຮກ. Hashing ແມ່ນວິທີທີ່ເປັນໄປໄດ້ໂດຍຜ່ານການທີ່ພວກເຮົາສາມາດຫຼຸດຜ່ອນຄວາມສັບສົນຂອງເວລາຂອງພວກເຮົາ. ມັນຄ່າໃຊ້ຈ່າຍ O (n) ຄວາມສັບສົນທີ່ໃຊ້ເວລາ.

ພວກເຮົາຈະນັບແລະເກັບຮັກສາຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບໃນແຜນທີ່ຂອງພວກເຮົາ. ສົມມຸດວ່າອົງປະກອບໃດ ໜຶ່ງ ມາ 3 ເທື່ອໃນຂບວນທີ່ພວກເຮົາ ກຳ ນົດຄວາມຖີ່ຂອງມັນເປັນ 3, ພ້ອມກັບອົງປະກອບນັ້ນ. HashMap ສາມາດຖືກ ນຳ ໃຊ້ເພື່ອຈຸດປະສົງນີ້ເພື່ອເກັບຮັກສາລະຫັດແລະຄ່າຕ່າງໆ. ພວກເຮົາຈະເກັບຮັກສາອົງປະກອບທັງ ໝົດ ເປັນກຸນແຈແລະຄວາມຖີ່ຂອງມັນເປັນຄ່າໃນ HashMap. ຫຼັງຈາກນັ້ນ, ພວກເຮົາຈະ ດຳ ເນີນວົງແລະລ້ຽວແຖວຂອງອາເລແລະເອົາແຕ່ລະອົງປະກອບແລະກວດເບິ່ງຄວາມຖີ່ຂອງມັນ. ຖ້າຄວາມຖີ່ຂອງອົງປະກອບໃດ ໜຶ່ງ ພົບວ່າເທົ່າກັບ k, ຫຼັງຈາກນັ້ນພວກເຮົາກໍ່ຈະສົ່ງຄືນອົງປະກອບນັ້ນ. ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງຜ່ານແຖວ, ດັ່ງນັ້ນຖ້າວ່າອົງປະກອບພົບກັບເວລາ k ທີ່ເກີດຂື້ນ. ຫຼັງຈາກນັ້ນແນ່ນອນມັນຈະເປັນອົງປະກອບ ທຳ ອິດທີ່ມີ k ບໍ່ເກີດຂື້ນ.

ຂໍໃຫ້ເຮົາພິຈາລະນາຕົວຢ່າງ:

arr [] = {2,4,6,4,2,1,}, k = 2

ພວກເຮົາຈະເກັບຮັກສາອົງປະກອບຕ່າງໆເປັນກຸນແຈແລະຄວາມຖີ່ຂອງມັນເປັນຄຸນຄ່າເຂົ້າໃນແຜນທີ່, ຫຼັງຈາກເກັບຮັກສາແຜນທີ່ຂອງພວກເຮົາຈະມີຄຸນຄ່າດັ່ງຕໍ່ໄປນີ້:

myMap={1:1, 2:2, 4:2, 6:1};

ພວກເຮົາຈະກວດສອບແຕ່ລະອົງປະກອບຂອງອາເລ, ເລີ່ມຈາກດັດຊະນີ 0th ພວກເຮົາຈະເລີ່ມຕົ້ນການຂ້າມແຖວ

i = 0,

ຖ້າຄວາມຖີ່ຂອງແຕ່ລະອາເລ [i] == k:

ຄວາມຖີ່ຂອງ 2 ແມ່ນ 2, ເຊິ່ງເທົ່າກັບ k ມັນກໍ່ແມ່ນສ່ວນປະກອບທີ່ມາກ່ອນ k ບໍ່ເກີດຂື້ນ, ດັ່ງນັ້ນພວກເຮົາສົ່ງຄືນມາ [i] ແລະຜົນຜະລິດຂອງພວກເຮົາຈະເປັນ 2

ໃນກໍລະນີຖ້າຄວາມຖີ່ຂອງຄວາມຖີ່ຂອງອົງປະກອບ ໜຶ່ງ ບໍ່ກົງກັບ 'k', ພວກເຮົາຈະກັບຄືນ -1.

ລະຫັດ

ລະຫັດ C ++ ເພື່ອຊອກຫາອົງປະກອບ ທຳ ອິດທີ່ເກີດຂື້ນ k ເທື່ອໃນແຖວ

#include<iostream>
#include <unordered_map>

using namespace std;

int firstElement(int arr[], int n, int k)
{
    unordered_map<int, int> freqMap;

    for (int i=0; i<n; i++)
        freqMap[arr[i]]++;

    for (int i=0; i<n; i++)
        if (freqMap[arr[i]] == k)
            return arr[i];

    return -1;
}
int main()
{
    int arr[] = {2,4,6,4,2,1,6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
    cout << firstElement(arr, n, k);
    return 0;
}
2

ລະຫັດ Java ເພື່ອຊອກຫາອົງປະກອບ ທຳ ອິດທີ່ເກີດຂື້ນ k ເທື່ອໃນແຖວ

import java.util.HashMap;

class firstKOccuringElement
{
    public static int getFirstElement(int arr[], int n, int k)
    {
        HashMap<Integer, Integer> freqMap = new HashMap<>();
        for (int i = 0; i < n; i++)
        {
            int a = 0;
            if(freqMap.containsKey(arr[i]))
            {
                freqMap.put(arr[i], freqMap.get(arr[i])+1);
            }
            else
            {
                freqMap.put(arr[i], 1);
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (freqMap.get(arr[i]) == k)
            {
                return arr[i];
            }
        }
        return -1;
    }
    public static void main(String[] args)
    {
        int arr[] = {2,4,6,4,2,1,6};
        int n = arr.length;
        int k = 2;
        System.out.println(getFirstElement(arr, n, k));
    }
}
2

ການວິເຄາະຄວາມສັບສົນ

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ນີ້, ຍ້ອນວ່າພວກເຮົາໄດ້ ນຳ ໃຊ້ hashmap ພວກເຮົາສາມາດ ດຳ ເນີນການປະຕິບັດງານໃນເວລາ O (1).

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ໃນກໍລະນີທີ່ຮ້າຍແຮງທີ່ສຸດເມື່ອອົງປະກອບທັງ ໝົດ ແຕກຕ່າງ. ພວກເຮົາຈະຕ້ອງເກັບເອົາອົງປະກອບ N ທັງ ໝົດ ເຂົ້າໃນແຜນທີ່ເຊິ່ງຈະໃຊ້ເວລາຫວ່າງເປັນເສັ້ນ.