ການປະຕິບັດງານຂັ້ນຕ່ ຳ ເພື່ອເຮັດໃຫ້ອົງປະກອບທັງ ໝົດ ມີຄວາມເທົ່າທຽມກັນເປັນແຖວ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon BlackRock Citadel Directi Flipkart ແທ້ຈິງແລ້ວ Yandex
Array ແຮກ

ບັນຫາ“ ການ ດຳ ເນີນງານຂັ້ນຕ່ ຳ ທີ່ຈະເຮັດໃຫ້ທຸກໆອົງປະກອບເທົ່າທຽມກັນໃນແຖວ” ທີ່ທ່ານໄດ້ມອບໃຫ້ array ກັບບາງຄົນ integers ໃນ​ມັນ. ທ່ານຕ້ອງຊອກຫາວິທີການ ດຳ ເນີນງານຂັ້ນຕ່ ຳ ສຸດທີ່ສາມາດເຮັດໄດ້ເພື່ອເຮັດໃຫ້ຂບວນເທົ່າທຽມກັນ.

ຍົກຕົວຢ່າງ

ການປະຕິບັດງານຂັ້ນຕ່ ຳ ເພື່ອເຮັດໃຫ້ອົງປະກອບທັງ ໝົດ ມີຄວາມເທົ່າທຽມກັນເປັນແຖວ

[ 1,3,2,4,1]
3

ຄໍາອະທິບາຍ

ບໍ່ວ່າຈະມີ 3 ຕົວແປສາມາດເຮັດໄດ້ຫລື 3 ເພີ່ມເຕີມສາມາດເຮັດໄດ້ເພື່ອເຮັດໃຫ້ເປັນຂບວນເທົ່າທຽມກັນ.

[5,3,2,4,1]
4

ຄໍາອະທິບາຍ

ບໍ່ວ່າຈະມີ 4 ຕົວແປສາມາດເຮັດໄດ້ຫລື 4 ເພີ່ມເຕີມສາມາດເຮັດໄດ້ເພື່ອເຮັດໃຫ້ເປັນຂບວນເທົ່າທຽມກັນ.

ສູດການຄິດໄລ່ເພື່ອຊອກຫາການ ດຳ ເນີນງານຂັ້ນຕ່ ຳ ເພື່ອເຮັດໃຫ້ທຸກໆອົງປະກອບເທົ່າທຽມກັນ

  1. ປະກາດກ ແຜນທີ່.
  2. ໃນຂະນະທີ່ຂ້ອຍ <n, loop ສືບຕໍ່
    1. ເກັບຮັກສາອົງປະກອບຂບວນແລະຄວາມຖີ່ຂອງແຕ່ລະອົງປະກອບເຂົ້າໃນແຜນທີ່.
  3. ທີ່ກໍານົດໄວ້ “ maxCount” to 0
  4. ປະສົມປະສານໃນໄລຍະກວດກາເບິ່ງວ່າຖ້າມີ “ maxCount” ແມ່ນ ໜ້ອຍ ກວ່າມູນຄ່າຂອງຄີໃນແຜນທີ່
    1. ຖ້າສະພາບການພໍໃຈ, ຫຼັງຈາກນັ້ນໃຫ້ຕັ້ງຄ່າ “ maxCount” ກັບຄຸນຄ່າຂອງກຸນແຈ.
  5. ກັບຄືນ (n -“ maxCount”).

ຄໍາອະທິບາຍ

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

ພວກເຮົາ ກຳ ລັງຈະຊອກຫາອົງປະກອບທີ່ມີຄວາມຖີ່ສູງສຸດແລະພວກເຮົາກັບຄືນຄວາມແຕກຕ່າງລະຫວ່າງຄວາມຍາວຂອງຂບວນແລະ ຈຳ ນວນຄວາມຖີ່ສູງສຸດເພາະວ່າພວກເຮົາມີອົງປະກອບທີ່ມີຢູ່ໃນຂບວນທີ່ຊ້ ຳ ແລ້ວຊ້ ຳ ຈຶ່ງຈະໃຊ້ເວລາປະຕິບັດງານ ໜ້ອຍ ເພື່ອເຮັດໃຫ້ທຸກໆອົງປະກອບເປັນຄືກັນ ຍ້ອນວ່າມັນມີຫຼາຍກ່ວາການປ່ຽນແປງສະເພາະແລະນັ້ນແມ່ນເຫດຜົນທີ່ (ຄວາມຖີ່ຂອງຄວາມຖີ່ - ຄວາມຖີ່ສູງສຸດ) ມັນເຮັດວຽກຢູ່ທີ່ນີ້.

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

ຍົກຕົວຢ່າງ

arr: {1, 5, 2, 1, 3, 2, 1};

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

i = 0,

ມາຮອດ [i] = 1

countFreq = [1: 1]

i = 1

ມາຮອດ [i] = 5

countFreq = [1: 1,5: 1]

i = 2

ມາຮອດ [i] = 2

countFreq = [1: 1,5: 1,2: 1]

i = 3

ມາຮອດ [i] = 1

countFreq = [1: 2,5: 1,2: 1] => ໃນທີ່ນີ້ພວກເຮົາຈະພົບເຫັນອົງປະກອບ "1" ສອງເທື່ອດັ່ງນັ້ນຈະເພີ່ມ ຈຳ ນວນຄວາມຖີ່ຂອງ 1.

i = 4

ມາຮອດ [i] = 3

countFreq=[1:2,5:1,2:1,3:1]

i = 5

ມາຮອດ [i] = 2

countFreq = [1: 2,5: 1,2: 2: 3: 1] => ໃນທີ່ນີ້ພວກເຮົາຈະພົບເຫັນອົງປະກອບ "2" ສອງເທື່ອດັ່ງນັ້ນຈະເຮັດໃຫ້ ຈຳ ນວນຄວາມຖີ່ຂອງ 2 ເພີ່ມຂື້ນ.

i = 6

ມາຮອດ [i] = 1

countFreq = [1: 3,5: 1,2: 2: 3: 1] => ໃນທີ່ນີ້ພວກເຮົາຈະພົບເຫັນອົງປະກອບ "1" ສາມເທົ່າດັ່ງນັ້ນຈະເພີ່ມ ຈຳ ນວນຄວາມຖີ່ຂອງ 1.

ຕອນນີ້ເລີ່ມຕົ້ນ “ maxCount” ເຖິງ 0. ແລະກວດເບິ່ງຄວາມຖີ່ຂອງແຕ່ລະຖ້າມັນໃຫຍ່ກວ່າ “ maxCount”, ຖ້າເຫັນວ່າໃຫຍ່ກວ່າ, ຫຼັງຈາກນັ້ນເກັບມູນຄ່າຂອງຄວາມຖີ່ດັ່ງກ່າວໄວ້ “ maxCount”

ໃນທີ່ສຸດ, ພວກເຮົາຈະມີຄວາມຖີ່ສູງສຸດ “ maxCount”.

ພວກເຮົາກັບຄືນ n- “ maxCount” => 7-3 = 4, ນັ້ນແມ່ນພວກເຮົາຄວນເຮັດຢ່າງ ໜ້ອຍ 4 ປະຕິບັດການເພື່ອເຮັດໃຫ້ອາເລນເທົ່າທຽມກັນ.

ລະຫັດ

C ++ ເພື່ອຊອກຫາການ ດຳ ເນີນງານຂັ້ນຕ່ ຳ ເພື່ອເຮັດໃຫ້ທຸກໆອົງປະກອບມີຄວາມເທົ່າທຽມກັນເປັນແຖວ

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

int getMinimumOperation (int arr[], int n)
{
  unordered_map<int, int> countFreq;
  for (int i=0; i<n; i++)
    countFreq[arr[i]]++;

  int maxCount = 0;
  for (auto i : countFreq)
    if (maxCount < i.second)
      maxCount = i.second;

  return (n - maxCount);
}
int main()
{
  int arr[] = {1, 5, 2, 1, 3, 2, 1};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << getMinimumOperation(arr, n);
  return 0;
}
4

ລະຫັດ Java ເພື່ອຊອກຫາການ ດຳ ເນີນງານຂັ້ນຕ່ ຳ ເພື່ອເຮັດໃຫ້ທຸກໆອົງປະກອບມີຄວາມເທົ່າທຽມກັນເປັນແຖວ

import java.util.*;
class minimumOperations
{
    public static int getMinimumOperations(int arr[], int n)
    {
        HashMap<Integer, Integer> countFreq = new HashMap<Integer, Integer>();

        for (int i=0; i<n; i++)
        {
            if(countFreq.containsKey(arr[i]))
            {
                countFreq.put(arr[i], countFreq.get(arr[i])+1);
            }
            else
            {
                countFreq.put(arr[i], 1);
            }
        }
        int maxCount = 0;

        Set<Integer> s = countFreq.keySet();

        for (int i : s)
            if (maxCount < countFreq.get(i))
                maxCount = countFreq.get(i);


        return (n - maxCount);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 5, 2, 1, 3, 2, 1};
        int n = arr.length;
        System.out.println(getMinimumOperations(arr, n));
    }
}
4

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

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.

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

O (n) ບ່ອນທີ່ "n" ແມ່ນ ຈຳ ນວນຂອງອົງປະກອບໃນແຖວ.