ໂຊລູຊັ່ນສ່ວນປະກອບ Leetcode


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ Atlassian Bloomberg ເຟສບຸກ GoDaddy ກູໂກ Microsoft Oracle ສ່ວນ SnapChat Yahoo Zenefits
ແບ່ງແລະເອົາຊະນະ ແຮກ

ຖະແຫຼງການບັນຫາ

ພວກເຮົາໄດ້ຮັບ array ຂອງເລກເຕັມ. ພວກເຮົາ ຈຳ ເປັນຕ້ອງສົ່ງເລກເຕັມຄືນທີ່ເກີດຂື້ນຫຼາຍກ່ວາເວລາ⌋N / 2 the ໃນແຖວບ່ອນທີ່⌊⌋ແມ່ນຜູ້ປະຕິບັດງານພື້ນ. ອົງປະກອບນີ້ເອີ້ນວ່າອົງປະກອບສ່ວນໃຫຍ່. ໃຫ້ສັງເກດວ່າຂບວນການປ້ອນຂໍ້ມູນມີສ່ວນປະກອບສ່ວນໃຫຍ່ຢູ່ສະ ເໝີ.

ຍົກຕົວຢ່າງ

Array = {1 , 3 , 3 , 3}
3

ການປຽບທຽບ: ⌊N / 2⌋ = 4/2 = 2. ແລະເລກເຕັມ '3' ເກີດຂື້ນ 3 ເທົ່າໃນຂບວນ.

Array = {1 , 1 , 2}
1

ຄໍາອະທິບາຍ: ⌊N / 2⌋ = ⌊3 / 2⌋ = 1. ແລະ '1' ເກີດຂື້ນ 2 ຄັ້ງໃນແຖວ.

ວິທີການ (Hashtable)

ພວກເຮົາສາມາດເກັບຮັກສາຄວາມຖີ່ຂອງທຸກໆອົງປະກອບໃນຂບວນໃນຕາຕະລາງ hash. ຫຼັງຈາກນັ້ນມັນຈະງ່າຍຕໍ່ການກວດສອບຕົວເລກຄວາມຖີ່ຂອງ ຈຳ ນວນ> >N / 2⌋.

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນຕາຕະລາງ hash ເພື່ອເກັບ ກຳ ຄວາມຖີ່ຂອງເລກເຕັມໃນຂບວນ: ຄວາມຖີ່
  2. ສຳ ລັບທຸກໆອົງປະກອບ, i, ໃນຂບວນການ:
    • ເພີ່ມຂຶ້ນ ຄວາມຖີ່ [i] ຫຼືຕັ້ງ ຄວາມຖີ່ [i] = 0 ຖ້າມັນບໍ່ຢູ່ໃນຕາຕະລາງຢູ່ແລ້ວ
    •  If ຄວາມຖີ່ [i] > N / 2:
      • ກັບຄືນ i
  3. ກັບຄືນ -1 (ເພື່ອຫລີກລ້ຽງຄວາມຜິດພາດຂອງການລວບລວມ)
  4. ພິມຜົນໄດ້ຮັບ

ການປະຕິບັດວິທີແກ້ໄຂສ່ວນໃຫຍ່ຂອງອົງປະກອບ Leetcode

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;

int majorityElement(vector <int> &a)
{
    int majorityCount = ((int) a.size()) / 2;
    unordered_map <int , int> frequency;
    for(int &i : a)
    {
        if(++frequency[i] > majorityCount)
            return i;
    }
    return -1;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

ໂຄງການ Java

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        HashMap <Integer , Integer> frequency = new HashMap<>();
        for(int i = 0 ; i < a.length ; i++)
        {
            frequency.put(a[i] , frequency.getOrDefault(a[i] , 0) + 1);
            if(frequency.get(a[i]) > a.length / 2)
                return a[i];
        }
        return -1;
    }
}
2

ການວິເຄາະຄວາມສັບສົນຂອງສ່ວນໃຫຍ່ຂອງອົງປະກອບ Leetcode Solution

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

ໂອ (N) ດັ່ງທີ່ພວກເຮົາລວບລວມຂບວນ ໜຶ່ງ ຄັ້ງເພື່ອຊອກຫາສ່ວນປະກອບສ່ວນໃຫຍ່. N = ຂະ ໜາດ ຂອງຂບວນ.

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

ໂອ (N) ເປັນ ຈຳ ນວນສູງສຸດຂອງສ່ວນປະກອບທີ່ແຕກຕ່າງໃນອາເລສາມາດ: N - ⌊N / 2⌋ ເປັນອົງປະກອບສ່ວນໃຫຍ່ຄອບຄອງຢ່າງ ໜ້ອຍ ⌊ບໍ່ / 2⌋ ຕົວຊີ້ວັດ. ເພາະສະນັ້ນ, ຄວາມສັບສົນໃນອະວະກາດແມ່ນເປັນເສັ້ນ.

ວິທີການ (ສູດການຄິດໄລ່ການອອກສຽງ Boyer-Moore)

ບັນຫານີ້ເປັນຕົວຢ່າງທີ່ດີຂອງວິທີທີ່ພວກເຮົາສາມາດຊອກຫາສ່ວນປະກອບສ່ວນໃຫຍ່ໃນກະແສຂອງອົງປະກອບຕ່າງໆ. ສູດການຄິດໄລ່ການອອກສຽງຂອງ Boyer-Moore ແມ່ນໃຊ້ເພື່ອຊອກຫາອົງປະກອບທີ່ຄອບຄອງຫຼາຍກວ່າ⌋N / 2⌋ທີ່ຢູ່ໃນ ລຳ ດັບ. ສູດການຄິດໄລ່ນີ້ຮັກສາກ ຜູ້ສະຫມັກ ແລະມັນ ນັບ ໃນຂບວນການ. ພວກເຮົາດໍາເນີນການຜ່ານດຽວຂອງແຖວກັບ ຜູ້ສະຫມັກ = -1 ແລະ ນັບ = 0. ຖ້າຫາກວ່າອົງປະກອບໃດ ໜຶ່ງ ທີ່ຢູ່ໃນຂບວນແມ່ນ the ຜູ້ສະຫມັກ, ພວກເຮົາເພີ່ມຂື້ນ ນັບ. ຖ້າບໍ່ດັ່ງນັ້ນ, ພວກເຮົາຫຼຸດມັນລົງ. ຖ້າການນັບກາຍເປັນສູນ, ພວກເຮົາຈະປ່ຽນຊື່ ຜູ້ສະຫມັກ ແລະຕັ້ງຄ່າຂອງມັນ ນັບ ກັບ 0.

ເພື່ອຈະເຂົ້າໃຈການເຮັດວຽກຂອງມັນ, ໃຫ້ເຮັດຕາມຕົວຢ່າງຂ້າງລຸ່ມນີ້:

ໂຊລູຊັ່ນສ່ວນປະກອບ Leetcode

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

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນສອງຕົວແປ: ຜູ້ສະຫມັກ ແລະ cnt ເພື່ອເກັບຮັກສາຜູ້ສະ ໝັກ ແລະຄວາມຖີ່ຂອງມັນ ສຳ ລັບທິດສະດີທີ່ກ່ຽວຂ້ອງ
  2. ດຽວນີ້, ສຳ ລັບທຸກໆອົງປະກອບ i ໃນຂບວນການ:
    • If cnt ເທົ່າກັບສູນ:
      • ອັບເດດ: ຜູ້ສະ ໝັກ = i
    • If i ເທົ່າກັບ ຜູ້ສະຫມັກ:
      • ການເພີ່ມຂື້ນ cnt: cnt ++
    • ອື່ນ:
      • ຫຼຸດລົງ cnt: cnt–
  3. Return ຜູ້ສະຫມັກ
  4. ພິມຜົນໄດ້ຮັບ

ການປະຕິບັດວິທີແກ້ໄຂສ່ວນໃຫຍ່ຂອງອົງປະກອບ Leetcode

ໂຄງການ C ++

#include <bits/stdc++.h>
using namespace std;

int majorityElement(vector <int> &a)
{
    int candidate = -1 , cnt = 0;
    for(int &i : a)
    {
        if(cnt == 0)
            candidate = i;
        cnt += (candidate == i) ? 1 : -1;
    }
    return candidate;
}

int main()
{
    vector <int> a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
    cout << majorityElement(a) << '\n';
    return 0;
}

ໂຄງການ Java

import java.util.*;

class majority_element
{
    public static void main(String args[])
    {
        int[] a = {1 , 1 , 2 , 2 , 1 , 2 , 2};
        System.out.println(majorityElement(a));
    }

    static int majorityElement(int[] a)
    {
        int candidate = -1 , cnt = 0;
        for(int i = 0 ; i < a.length ; i++)
        {
            if(cnt == 0)
                candidate = a[i];
            cnt += (candidate == a[i]) ? 1 : -1;
        }
        return candidate;
    }
}
2

ການວິເຄາະຄວາມສັບສົນຂອງສ່ວນໃຫຍ່ຂອງອົງປະກອບ Leetcode Solution

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

ໂອ (N) ດັ່ງທີ່ພວກເຮົາ traverse ອາເລທັງຫມົດຄັ້ງ. ທີ່ນີ້, N = ຂະ ໜາດ ຂອງຂບວນ.

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

O (1) ດັ່ງທີ່ພວກເຮົາໃຊ້ພື້ນທີ່ ໜ່ວຍ ຄວາມ ຈຳ ຄົງທີ່.