ಶ್ರೇಣಿಯಲ್ಲಿ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಸಮಾನವಾಗಿಸಲು ಕನಿಷ್ಠ ಕಾರ್ಯಾಚರಣೆ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಕಪ್ಪು ಕಲ್ಲು ಸಿಟಾಡೆಲ್ ಡೈರೆಕ್ಟಿ ಫ್ಲಿಪ್ಕಾರ್ಟ್ ವಾಸ್ತವವಾಗಿ ಯಾಂಡೆಕ್ಸ್
ಅರೇ ಹ್ಯಾಶಿಂಗ್

"ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಶ್ರೇಣಿಯಲ್ಲಿ ಸಮಾನವಾಗಿಸಲು ಕನಿಷ್ಠ ಕಾರ್ಯಾಚರಣೆ" ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಸರಣಿ ಕೆಲವು ಪೂರ್ಣಾಂಕಗಳು ಅದರಲ್ಲಿ. ಶ್ರೇಣಿಯನ್ನು ಸಮಾನವಾಗಿಸಲು ಮಾಡಬಹುದಾದ ಕನಿಷ್ಠ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ನೀವು ಕಂಡುಹಿಡಿಯಬೇಕು.

ಉದಾಹರಣೆ

ಶ್ರೇಣಿಯಲ್ಲಿ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಸಮಾನವಾಗಿಸಲು ಕನಿಷ್ಠ ಕಾರ್ಯಾಚರಣೆ

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

ವಿವರಣೆ

ಒಂದೋ 3 ವ್ಯವಕಲನಗಳನ್ನು ಮಾಡಬಹುದು ಅಥವಾ ಸಮಾನ ಸೇರ್ಪಡೆ ಮಾಡಲು 3 ಸೇರ್ಪಡೆಗಳನ್ನು ಮಾಡಬಹುದು.

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

ವಿವರಣೆ

ಒಂದೋ 4 ವ್ಯವಕಲನಗಳನ್ನು ಮಾಡಬಹುದು ಅಥವಾ ಸಮಾನ ಸೇರ್ಪಡೆ ಮಾಡಲು 4 ಸೇರ್ಪಡೆಗಳನ್ನು ಮಾಡಬಹುದು.

ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಸಮಾನವಾಗಿಸಲು ಕನಿಷ್ಠ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಅಲ್ಗಾರಿದಮ್

  1. ಎ ಘೋಷಿಸಿ ನಕ್ಷೆ.
  2. ನಾನು <n, ಲೂಪ್ ಮುಂದುವರಿಯುತ್ತದೆ
    1. ಪ್ರತಿಯೊಂದು ಅಂಶದ ರಚನೆಯ ಅಂಶ ಮತ್ತು ಆವರ್ತನಗಳನ್ನು ನಕ್ಷೆಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ.
  3. ಹೊಂದಿಸಿ “ಗರಿಷ್ಠ ಲೆಕ್ಕ” 0 ಗೆ.
  4. ಎಂದು ಲೂಪ್ ಚೆಕ್ ಮೇಲೆ ಪುನರಾವರ್ತನೆ “ಗರಿಷ್ಠ ಲೆಕ್ಕ” ನಕ್ಷೆಯಲ್ಲಿನ ಕೀಲಿಯ ಮೌಲ್ಯಕ್ಕಿಂತ ಕಡಿಮೆಯಾಗಿದೆ
    1. ಸ್ಥಿತಿಯು ತೃಪ್ತಿಪಡಿಸಿದರೆ, ನಂತರ ಹೊಂದಿಸಿ “ಗರಿಷ್ಠ ಲೆಕ್ಕ” ಕೀಲಿಯ ಮೌಲ್ಯಕ್ಕೆ.
  5. ಹಿಂತಿರುಗಿ (n - “maxCount”).

ವಿವರಣೆ

ನಮಗೆ ಒಂದು ಇದೆ ಪೂರ್ಣಾಂಕ ಸರಣಿ ಇನ್ಪುಟ್ ಆಗಿ. ಒಂದು ಶ್ರೇಣಿಯನ್ನು ಸಮಾನವಾಗಿಸಲು ಮಾಡಬಹುದಾದ ಕನಿಷ್ಠ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ನಮ್ಮ ಕಾರ್ಯ. ನಾವು ಅದರಲ್ಲಿ ನಕ್ಷೆಯನ್ನು ಬಳಸಲಿದ್ದೇವೆ. ನಕ್ಷೆಯನ್ನು ಬಳಸುವುದರಿಂದ, ನಾವು ಅಂಶಗಳನ್ನು ಅವುಗಳ ಆವರ್ತನಗಳೊಂದಿಗೆ ಸುಲಭವಾಗಿ ಸಂಗ್ರಹಿಸಬಹುದು, ಏಕೆಂದರೆ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಆವರ್ತನಗಳು ಪ್ರಮುಖ ಪಾತ್ರವಹಿಸುತ್ತವೆ.

ನಾವು ಗರಿಷ್ಠ ಆವರ್ತನದೊಂದಿಗೆ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಹೊರಟಿದ್ದೇವೆ ಮತ್ತು ರಚನೆಯ ಉದ್ದ ಮತ್ತು ಗರಿಷ್ಠ ಆವರ್ತನ ಎಣಿಕೆಯ ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ನಾವು ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ ಏಕೆಂದರೆ ನಾವು ಈಗಾಗಲೇ ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿರುವ ಅಂಶವನ್ನು ಪುನರಾವರ್ತಿಸಿದ್ದೇವೆ, ಆದ್ದರಿಂದ ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಒಂದೇ ರೀತಿ ಮಾಡಲು ಕಡಿಮೆ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತದೆ ಅದು ನಿರ್ದಿಷ್ಟತೆಯನ್ನು ಬದಲಿಸುವ ಬದಲು ಮತ್ತು ಅದಕ್ಕಾಗಿಯೇ (ರಚನೆಯ ಉದ್ದ- ಗರಿಷ್ಠ ಆವರ್ತನ) ಅದು ಇಲ್ಲಿ ಕಾರ್ಯನಿರ್ವಹಿಸುತ್ತದೆ.

ಇಲ್ಲಿ ಒಂದು ಉದಾಹರಣೆಯನ್ನು ಪರಿಗಣಿಸೋಣ:

ಉದಾಹರಣೆ

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

ಮೊದಲ ಅತ್ಯಂತ ಅಂಶದಿಂದ ಪ್ರಾರಂಭಿಸಿ, ನಾವು ಇಡೀ ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಪ್ರತಿ ಅಂಶದ ಆವರ್ತನವನ್ನು ಎಣಿಸುತ್ತೇವೆ ಮತ್ತು ಅದನ್ನು ನಕ್ಷೆಯಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ.

i = 0,

arr [i] = 1

countFreq = [1: 1]

i = 1

arr [i] = 5

countFreq = [1: 1,5: 1]

i = 2

arr [i] = 2

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

i = 3

arr [i] = 1

countFreq = [1: 2,5: 1,2: 1] => ಇಲ್ಲಿ ನಾವು “1” ಅಂಶವನ್ನು ಎರಡು ಬಾರಿ ಕಾಣುತ್ತೇವೆ ಆದ್ದರಿಂದ ಆವರ್ತನ ಎಣಿಕೆ 1 ಅನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ.

i = 4

arr [i] = 3

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

i = 5

arr [i] = 2

countFreq = [1: 2,5: 1,2: 2: 3: 1] => ಇಲ್ಲಿ ನಾವು “2” ಅಂಶವನ್ನು ಎರಡು ಬಾರಿ ಕಾಣುತ್ತೇವೆ ಆದ್ದರಿಂದ ಆವರ್ತನ ಎಣಿಕೆ 2 ಅನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ.

i = 6

arr [i] = 1

countFreq = [1: 3,5: 1,2: 2: 3: 1] => ಇಲ್ಲಿ ನಾವು “1” ಅಂಶವನ್ನು ಮೂರು ಬಾರಿ ಕಾಣುತ್ತೇವೆ ಆದ್ದರಿಂದ ಆವರ್ತನ ಎಣಿಕೆ 1 ಅನ್ನು ಹೆಚ್ಚಿಸುತ್ತದೆ.

ಈಗ ಪ್ರಾರಂಭಿಸಿ “ಗರಿಷ್ಠ ಲೆಕ್ಕ” ಗೆ 0. ಮತ್ತು ಪ್ರತಿ ಆವರ್ತನಕ್ಕಿಂತ ದೊಡ್ಡದಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ “ಗರಿಷ್ಠ ಲೆಕ್ಕ”, ಹೆಚ್ಚಿನದಾಗಿದೆ ಎಂದು ಕಂಡುಕೊಂಡರೆ, ಆ ಆವರ್ತನದ ಮೌಲ್ಯವನ್ನು ಇಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ “ಗರಿಷ್ಠ ಲೆಕ್ಕ”

ಕೊನೆಗೆ, ನಾವು ಹೆಚ್ಚಿನ ಆವರ್ತನವನ್ನು ಹೊಂದಿರುತ್ತೇವೆ “ಗರಿಷ್ಠ ಲೆಕ್ಕ”.

ನಾವು n- ಅನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ “ಗರಿಷ್ಠ ಲೆಕ್ಕ” => 7-3 = 4, ಅಂದರೆ ನಾವು ರಚನೆಯನ್ನು ಸಮಾನವಾಗಿಸಲು ಕನಿಷ್ಠ 4 ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಮಾಡಬೇಕು.

ಕೋಡ್

ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಶ್ರೇಣಿಯಲ್ಲಿ ಸಮಾನವಾಗಿಸಲು ಕನಿಷ್ಠ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++

#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

ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ಶ್ರೇಣಿಯಲ್ಲಿ ಸಮಾನವಾಗಿಸಲು ಕನಿಷ್ಠ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.