ແຍກຕ່າງຫາກອົງປະກອບທີ່ຢູ່ຕິດກັນໃນຂບວນ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Coursera DE Shaw hike IBM ກຸລະກິ ນາກາໂຣ Opera ຫ້ອງ OYO Zoho
Array

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

ສົມມຸດວ່າພວກເຮົາມີ integer array. ບັນຫາ“ ແຍກຕ່າງຫາກບັນດາອົງປະກອບທີ່ຢູ່ຕິດກັນໃນອາເລ” ຖາມເພື່ອ ກຳ ນົດວ່າມັນເປັນໄປໄດ້ບໍ່ທີ່ຈະເອົາຕົວເລກທີ່ຢູ່ໃກ້ຄຽງທັງ ໝົດ ແຕກຕ່າງກັນຫຼືບໍ່ໂດຍການແລກປ່ຽນສອງສ່ວນທີ່ຢູ່ຕິດກັນຫລືໃກ້ຄຽງໃນແຖວຖ້າເປັນໄປໄດ້ຈາກນັ້ນພິມ“ YES. ” ອື່ນພິມ“ ບໍ່”.

ຍົກຕົວຢ່າງ

arr[] = { 3,5,5,3,5}
YES

ໃນຕົວຢ່າງນີ້, ພວກເຮົາສາມາດໄດ້ຮັບບັນດາຕົວເລກທີ່ຢູ່ໃກ້ຄຽງທີ່ແຕກຕ່າງກັນໂດຍການລ້ຽວເຂົ້າຂອງ [2] ແລະຮອດ [3] ເປັນ 5 ແລະ 2 ຕາມ ລຳ ດັບ.

ແຍກຕ່າງຫາກອົງປະກອບທີ່ຢູ່ຕິດກັນໃນຂບວນ

arr[] = {3 , 5,  3, 3 }
NO

ຄໍາອະທິບາຍ

ພວກເຮົາບໍ່ສາມາດໄດ້ຮັບແຖວທີ່ຕ້ອງການເຖິງແມ່ນວ່າຫລັງຈາກໄດ້ແລກປ່ຽນຄຸນຄ່າແລ້ວ.

ສູດການຄິດໄລ່ ສຳ ລັບອົງປະກອບທີ່ຢູ່ຕິດກັນທີ່ແຕກຕ່າງກັນໃນແຖວ

1. Declare a map.
2. Count and store the frequencies of each element of the array.
3. Set maxFreq to 0.
4. Get the maximum frequency of a number from the map.
5. Check if maxFreq is greater than the half-length of the array, means maxFreq >(n+1) / 2.
    1. If true, then print NO.
    2. Else print YES.

ຄໍາອະທິບາຍ

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

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

ສຳ ລັບສິ່ງນັ້ນ, ພວກເຮົາຈະ ກຳ ລັງຜ່ານແຜນທີ່, ແລະກວດເບິ່ງແຕ່ລະອົງປະກອບ, ຖ້າພວກເຮົາມີຄວາມຖີ່ສູງກວ່າຄວາມຖີ່ທີ່ເກັບໄວ້ກ່ອນ ໜ້າ ນີ້. ດ້ວຍສິ່ງນີ້, ພວກເຮົາຈະມີຕົວເລກສູງສຸດເປັນຄວາມຖີ່, ແລະກວດເບິ່ງວ່າຄວາມຖີ່ນັ້ນສູງກວ່າເຄິ່ງ ໜຶ່ງ ຂອງຄວາມຍາວຂອງອາເລ. ຖ້າເປັນຄວາມຈິງ, ແລ້ວພິມ NO, ພິມອີກແລ້ວແມ່ນແລ້ວ.

ລະຫັດ

ລະຫັດ C ++ ສຳ ລັບອົງປະກອບທີ່ຢູ່ຕິດກັນທີ່ແຕກຕ່າງກັນໃນບັນຫາ array

#include<bits/stdc++.h>
using namespace std;
void areDistinctAdjacent(int a[], int n)
{
    unordered_map<int, int> MAP;
    for (int i = 0; i < n; ++i)
        MAP[a[i]]++;
    int maxFreq = 0;
    for (int i = 0; i < n; ++i)
        if (maxFreq < MAP[a[i]])
            maxFreq = MAP[a[i]];
    if (maxFreq > (n + 1) / 2)
        cout << "NO";
    else
        cout << "YES";
}
int main()
{
    int arr[] = { 3,5,5,3,5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    areDistinctAdjacent(arr, n);
    return 0;
}

 

YES

ລະຫັດ Java ສຳ ລັບອົງປະກອບທີ່ຢູ່ຕິດກັນທີ່ແຕກຕ່າງກັນໃນບັນຫາຂອງຂບວນ

import java.util.HashMap;
import java.util.Map;

class adjacentDistinctElement
{
    static void areDistinctAdjacent(int a[], int n)
    {
        HashMap<Integer,Integer> MAP = new HashMap<Integer,Integer>();

        for (int i = 0; i < n; ++i)
        {
            if(MAP.containsKey(a[i]))
            {
                int x = MAP.get(a[i]) + 1;
                MAP.put(a[i],x);
            }
            else
            {
                MAP.put(a[i],1);
            }

        }
        int maxFreq = 0;

        for (int i = 0; i < n; ++i)
            if (maxFreq < MAP.get(a[i]))
                maxFreq = MAP.get(a[i]);

        if (maxFreq > (n + 1) / 2)
        {
            System.out.println("NO");
        }
        else
        {
            System.out.println("YES");
        }
    }
    public static void main (String[] args)
    {
        int arr[] = { 3,5,5,3,5 };
        int n = arr.length;
        areDistinctAdjacent(arr, n);
    }
}

YES

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

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

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

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

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