ຊອກຫາສິ່ງທີ່ຊ້ ຳ ຊ້ອນກັນໃນແຖວທີ່ ກຳ ນົດໄວ້ເມື່ອອົງປະກອບຕ່າງໆບໍ່ ຈຳ ກັດຢູ່ໃນຂອບເຂດໃດ ໜຶ່ງ  


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Adobe Amazon ປັດໃຈ MAQ UHG Optum
Array ແຮກ

ບັນຫາ "ຊອກຫາຊໍ້າໃນອາເລທີ່ມອບໃຫ້ເມື່ອອົງປະກອບຕ່າງໆບໍ່ ຈຳ ກັດຢູ່ໃນຂອບເຂດໃດ ໜຶ່ງ" ລະບຸວ່າທ່ານມີ array ປະກອບມີ n integers. ຖະແຫຼງການບັນຫາມັນເພື່ອຊອກຫາອົງປະກອບທີ່ຊ້ ຳ ກັນຖ້າມີຢູ່ໃນຂບວນ. ຖ້າບໍ່ມີອົງປະກອບດັ່ງກ່າວກັບຄືນມາ -1.

ຍົກຕົວຢ່າງ  

ຊອກຫາສິ່ງທີ່ຊ້ ຳ ຊ້ອນກັນໃນແຖວທີ່ ກຳ ນົດໄວ້ເມື່ອອົງປະກອບຕ່າງໆບໍ່ ຈຳ ກັດຢູ່ໃນຂອບເຂດໃດ ໜຶ່ງPin

[ 2, 4, 6, 2, 7, 8, 9, 7]
2, 7

ຄໍາອະທິບາຍ

ໃນອາເລ 2 ແລະ 7 ນີ້ແມ່ນສ່ວນປະກອບທີ່ຊ້ ຳ ກັນ.

[134, 567, 134, 456, 1000, 567, 7]
134, 567

ຄໍາອະທິບາຍ

ໃນອາເລ 134 ແລະ 567 ນີ້ແມ່ນສ່ວນປະກອບທີ່ຊ້ ຳ ກັນ.

ສູດການຄິດໄລ່ເພື່ອຊອກຫາອົງປະກອບທີ່ຊ້ ຳ ກັນໃນແຖວ  

  1. ປະກາດ ແຜນທີ່.
  2. ເກັບຮັກສາອົງປະກອບຂອງອາເລແລະຄວາມຖີ່ຂອງມັນໄວ້ໃນແຜນທີ່.
  3. ປະກາດ ບົວບານ ຕົວແປ ຊ້ໍາ ເພື່ອກວດເບິ່ງວ່າມີອົງປະກອບທີ່ຊ້ ຳ ກັນຫຼືບໍ່.
  4. ເຊື່ອມສານຜ່ານແຜນທີ່ແລະກວດເບິ່ງວ່າອົງປະກອບໃດທີ່ມີຄວາມຖີ່ສູງກວ່າ 1.
  5. ຖ້າຄວາມຖີ່ສູງກ່ວາ 1, ພິມອົງປະກອບແລະເລີ່ມຕົ້ນຊ້ ຳ ກັບຄວາມຈິງ.
  6. ກວດເບິ່ງວ່າການຊໍ້າຊ້ອນບໍ່ຖືກຕ້ອງຖ້າສະພາບການພໍໃຈແລ້ວພິມພິມ -1.

ຄໍາອະທິບາຍ

ພວກເຮົາມີບັນຫາໃນການທີ່ພວກເຮົາຕ້ອງໄດ້ ກຳ ນົດອົງປະກອບທີ່ຊ້ ຳ ກັນໃນອາເລແລະພິມອົງປະກອບເຫຼົ່ານັ້ນ. ສຳ ລັບສິ່ງນີ້, ພວກເຮົາ ກຳ ລັງຈະໃຊ້ a HashMap ສຳ ລັບເກັບຮັກສາຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບຂບວນ. ຄວາມຖີ່, ເຊິ່ງມີຂະ ໜາດ ໃຫຍ່ກວ່າ 1, ໝາຍ ຄວາມວ່າຕົວເລກດັ່ງກ່າວເຮັດຊ້ ຳ ອີກໃນແຖວ. ນັ້ນ ໝາຍ ຄວາມວ່າຊ້ ຳ ກັບ ຈຳ ນວນນັ້ນ.

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

ພວກເຮົາໄດ້ຜ່ານສອງການໂຕ້ຖຽງເປັນຂບວນແລະຄວາມຍາວຂອງມັນ. ດຽວນີ້ປະກາດຕົວປ່ຽນ ໜຶ່ງ ອັນຕື່ມອີກເຊິ່ງຕົວແປ Boolean ຈະຖືກແປວ່າບໍ່ຖືກຕ້ອງ. ຫຼັງຈາກນັ້ນ, ກວດກາມັນຕໍ່ມາ, ຖ້າພວກເຮົາບໍ່ພົບເຫັນອົງປະກອບໃດ ໜຶ່ງ ທີ່ຊ້ ຳ ກັນແລ້ວ ຊ້ໍາ ຍັງບໍ່ຖືກຕ້ອງອີກຕໍ່ໄປມັນຈະເປັນຄວາມຈິງ. ຫຼັງຈາກນັ້ນ, ນຳ ໃຊ້ແຜນທີ່ນີ້, ຊອກຫາອົງປະກອບທີ່ມີຄວາມຖີ່ສູງກວ່າ 1, ພວກເຮົາຈະໄດ້ພິມສິ່ງເຫຼົ່ານັ້ນ. ແລະນັ້ນແມ່ນວິທີທີ່ພວກເຮົາຊອກຫາອົງປະກອບທີ່ຊ້ ຳ ກັນໃນແຖວ.

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

arr [] = {2,4,6,3,1,2,4,7};

i = 0, ມາຮອດ [i] = 2; freq = {2: 1}

i=1, arr[i]=4; freq={2:1,4:1}

i=2, arr[i]=6; freq={2:1,4:1,6:1}

i=3, arr[i]=3; freq={2:1,4:1,6:1,3:1}

i=4, arr[i]=1; freq={2:1,4:1,6:1,3:1,1:1}

i = 5, ມາຮອດ [i] = 2; freq = {2: 2,4: 1,6: 1,3: 1,1: 1} // ເພີ່ມຄວາມຖີ່ຂອງ '2' ຈາກ 1 ເຖິງ 2,

i = 6, ມາຮອດ [i] = 4; freq = {2: 2,4: 2,6: 1,3: 1,1: 1} // ເພີ່ມຄວາມຖີ່ຂອງ '4' ຈາກ 1 ເຖິງ 2,

i=7, arr[i]=7; freq={2:2,4:2,6:1,3:1,1:1,7:1}

ພວກເຮົາມີແບບແຜນທີ່: {2: 2,4: 2,6: 1,3: 1,1: 1,7: 1}

ດຽວນີ້ມີການປ່ຽນແປງຜ່ານແຜນທີ່, ແລະຊອກຫາວ່າຄ່າຄວາມຖີ່ໃດສູງກວ່າ 1, ພວກເຮົາເລີ່ມຕົ້ນທີ່ນີ້ມີການປ່ຽນແປງຕົວປ່ຽນແປງ Boolean ທີ່ບໍ່ຖືກຕ້ອງ, ດັ່ງນັ້ນເມື່ອພວກເຮົາກວດເບິ່ງວ່າຄວາມຖີ່ໃດສູງກວ່າ 1, ພວກເຮົາຈະປັບປຸງຊ້ ຳ ວ່າເປັນຄວາມຈິງ. ແລະຖ້າພວກເຮົາອອກຈາກ loop ມີຊ້ ຳ ທີ່ບໍ່ຖືກຕ້ອງ, ມັນ ໝາຍ ຄວາມວ່າອົງປະກອບທີ່ຊ້ ຳ ກັນບໍ່ມີຢູ່ໃນຂບວນ.

ຢ່າງຊັດເຈນ, 2 ແລະ 4 ມີຄວາມຖີ່ຫຼາຍກ່ວາ ໝາຍ ຄວາມວ່າພວກມັນແມ່ນອົງປະກອບທີ່ຊ້ ຳ ກັນ.

ແລະຜົນຜະລິດຂອງພວກເຮົາກາຍເປັນ [2 4]. ດັ່ງນັ້ນນີ້ແມ່ນຕົວຢ່າງຂອງວິທີທີ່ພວກເຮົາຊອກຫາອົງປະກອບທີ່ຊ້ ຳ ກັນໃນແຖວ.

ລະຫັດ  

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

#include <iostream>
#include <unordered_map>

using namespace std;

void getDuplicate(int arr[], int n)
{
    unordered_map<int,int> freq;

    for(int index=0;index<n;index++)
        freq[arr[index]]++;

    bool duplicate=false;
    unordered_map<int,int> :: iterator itr;
    for(itr=freq.begin();itr!=freq.end();itr++)
    {
        if(itr->second > 1)
        {
            cout<<itr->first<<" ";
            duplicate=true;
        }
    }
    if(!duplicate)
        cout<<"-1"<<endl;
}
int main()
{
    int arr[]={2,4,6,3,1,2,4,7};
    int n=sizeof(arr)/sizeof(arr[0]);
    getDuplicate(arr,n);
    return 0;
}
4 2

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

import java.util.HashMap;
class findDuplicateNumber
{
    public static void getDuplicate(int arr[], int n)
    {
        HashMap<Integer, Integer> freq=new HashMap<Integer, Integer>();
        for(int i=0; i<n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i],freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i],1);
            }
        }
        boolean duplicate=false;
        for(int i:freq.keySet())
        {
            if(freq.get(i)> 1)
            {
                System.out.print(i+" ");
                duplicate=true;
            }
        }
        if(!duplicate)
            System.out.println("-1");
    }
    public static void main(String [] args)
    {
        int arr[]= {2,4,6,3,1,2,4,7};
        int len=arr.length;
        getDuplicate(arr,len);
    }
}
2 4

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

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ. ດັ່ງນັ້ນ, "ຊອກຊໍ້າໃນອາເລທີ່ໃຫ້ເມື່ອອົງປະກອບຕ່າງໆບໍ່ ຈຳ ກັດຢູ່ໃນລະດັບໃດ ໜຶ່ງ" ບັນຫາມີຄວາມສັບສົນເວລາ.

ເບິ່ງ
ຊອກຫາຄູ່ທັງ ໝົດ (ກ, ຂ) ໃນຂອດດັ່ງກ່າວວ່າ a% b = k

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

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