ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಅತ್ಯಧಿಕ ಮತ್ತು ಕನಿಷ್ಠ ಆವರ್ತನಗಳ ನಡುವಿನ ವ್ಯತ್ಯಾಸ  


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

“ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಅತ್ಯಧಿಕ ಮತ್ತು ಕಡಿಮೆ ಆವರ್ತನಗಳ ನಡುವಿನ ವ್ಯತ್ಯಾಸ” ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ಒಂದು ಇದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಪೂರ್ಣಾಂಕ ಸರಣಿ. ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಎರಡು ವಿಭಿನ್ನ ಸಂಖ್ಯೆಗಳ ಅತ್ಯಧಿಕ ಆವರ್ತನ ಮತ್ತು ಕಡಿಮೆ ಆವರ್ತನದ ನಡುವಿನ ಗರಿಷ್ಠ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಮಸ್ಯೆ ಹೇಳಿಕೆಯು ಕೇಳುತ್ತದೆ.

ಉದಾಹರಣೆ  

ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಅತ್ಯಧಿಕ ಮತ್ತು ಕನಿಷ್ಠ ಆವರ್ತನಗಳ ನಡುವಿನ ವ್ಯತ್ಯಾಸಪಿನ್

arr[] = {1, 2, 3, 1, 5, 2, 3, 1 }
2

ವಿವರಣೆ

1 → 3 ಆವರ್ತನ (ಅತ್ಯಧಿಕ ಆವರ್ತನ)

5 → 1 ಆವರ್ತನ (ಕಡಿಮೆ ಆವರ್ತನ)

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

ವಿವರಣೆ

5 → 4 ಆವರ್ತನ (ಅತ್ಯಧಿಕ ಆವರ್ತನ)

3 → 1 ಆವರ್ತನ (ಕಡಿಮೆ ಆವರ್ತನ)

ಕ್ರಮಾವಳಿ  

  1. ಎ ಘೋಷಿಸಿ ನಕ್ಷೆ.
  2. ರಚನೆಯ ಅಂಶದ ಆವರ್ತನವನ್ನು ಸಂಗ್ರಹಿಸಿ ಮತ್ತು ಎಣಿಸಿ.
  3. ಹೊಂದಿಸಿ ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್ ಗೆ 0 ಮತ್ತು minfreq ಗೆ n.
  4. ನಕ್ಷೆಯಲ್ಲಿ ಸಂಚರಿಸಿ:
    1. ನಕ್ಷೆಯಲ್ಲಿ ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್ ಮತ್ತು ಆವರ್ತನದ ನಡುವಿನ ಗರಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ ಮತ್ತು ಅದನ್ನು ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್‌ಗೆ ಸಂಗ್ರಹಿಸಿ.
    2. ನಕ್ಷೆಯಲ್ಲಿ ಮಿನ್‌ಫ್ರೆಕ್ ಮತ್ತು ಆವರ್ತನದ ನಡುವಿನ ಕನಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ ಮತ್ತು ಅದನ್ನು ಮಿನ್‌ಫ್ರೆಕ್‌ಗೆ ಸಂಗ್ರಹಿಸಿ.
  5. ಹಿಂತಿರುಗಿ (ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್-ಮಿನ್‌ಫ್ರೆಕ್).

ವಿವರಣೆ

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

ಸಹ ನೋಡಿ
ಎಲ್ಲಾ ಸಬ್‌ರೇರ್‌ಗಳನ್ನು 0 ಮೊತ್ತದೊಂದಿಗೆ ಮುದ್ರಿಸಿ

ನಂತರ ನಾವು ಅದರ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿಸುತ್ತೇವೆ ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್ ಗೆ 0 ಮತ್ತು minfreq n ಗೆ, ಅಂದರೆ, ರಚನೆಯ ಉದ್ದವು ಯಾವುದೇ ಅಂಶವು ಕೊಟ್ಟಿರುವ ರಚನೆಯ ಗಾತ್ರಕ್ಕಿಂತ ಹೆಚ್ಚಿನ ಆವರ್ತನವನ್ನು ಹೊಂದಿರುವುದಿಲ್ಲ. ನಾವು ನಕ್ಷೆಯನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಒಂದೊಂದಾಗಿ ಎತ್ತಿಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು ಅದು ದೊಡ್ಡದಾದ ಅಥವಾ ಕಡಿಮೆ ಆವರ್ತನವನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಗರಿಷ್ಠ ಆವರ್ತನವನ್ನು ಬೇರೆ ವೇರಿಯೇಬಲ್‌ಗೆ ಮತ್ತು ಕನಿಷ್ಠ ಆವರ್ತನವನ್ನು ವಿಭಿನ್ನ ವೇರಿಯೇಬಲ್‌ಗೆ ಬೇರ್ಪಡಿಸಿ. ನಾವು ಗರಿಷ್ಠ ಆವರ್ತನ ಮತ್ತು ಕಡಿಮೆ ಆವರ್ತನದ ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಹಿಂದಿರುಗಿಸಬೇಕಾಗಿದೆ, ಆದ್ದರಿಂದ ನಾವು ಹಿಂತಿರುಗುತ್ತೇವೆ (ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್-ಮಿನ್‌ಫ್ರೆಕ್).

ನಾವು ಒಂದು ಉದಾಹರಣೆಯನ್ನು ತೆಗೆದುಕೊಳ್ಳೋಣ:

ಉದಾಹರಣೆ

arr [] = {1, 2, 3, 1, 5, 2, 3, 1}

ನಾವು ಮೊದಲು ಶ್ರೇಣಿಯನ್ನು ದಾಟಿದಾಗ, ನಾವು ಅಂಶವನ್ನು ಮತ್ತು ಅವುಗಳ ಯಾವುದೇ ಘಟನೆಗಳನ್ನು ನಕ್ಷೆಯಲ್ಲಿ ಇಡುತ್ತೇವೆ, ಸಂಚರಿಸಿದ ನಂತರ ನಾವು ನಕ್ಷೆಯನ್ನು ಹೀಗೆ ಹೊಂದುತ್ತೇವೆ:

ನಕ್ಷೆ: {1: 3, 2: 2, 3: 2, 5: 1}

ಈಗ, ನಾವು ನಕ್ಷೆಯಲ್ಲಿನ ಪ್ರತಿಯೊಂದು ಅಂಶದ ಘಟನೆಗಳನ್ನು ಹೊಂದಿದ್ದೇವೆ, ನಾವು ನಕ್ಷೆಯನ್ನು ಹಾದುಹೋಗಲು ಹೋಗುತ್ತೇವೆ ಮತ್ತು ನಕ್ಷೆಯಿಂದ ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಎತ್ತಿಕೊಂಡು ಅವುಗಳ ಆವರ್ತನವನ್ನು ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ಇದು ಹೆಚ್ಚಿನ ಪ್ರಸ್ತುತ ಆವರ್ತನ ಅಥವಾ ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್ ಮತ್ತು ಇದು ಕನಿಷ್ಠ ಪ್ರಸ್ತುತ ಆವರ್ತನ ಅಥವಾ minfreq ಮತ್ತು ಅದನ್ನು ಕ್ರಮವಾಗಿ maxfreq ಮತ್ತು minfreq ಗೆ ಸಂಗ್ರಹಿಸಿ.

  • 1: 3

3 ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್‌ಗಿಂತ ದೊಡ್ಡದಾಗಿದೆ, ಆದ್ದರಿಂದ ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್ = 3

3 ಮಿನ್‌ಫ್ರೆಕ್‌ಗಿಂತ ಚಿಕ್ಕದಾಗಿದೆ, ಆದ್ದರಿಂದ ಮಿನ್‌ಫ್ರೆಕ್ = 3

  • 2: 2

ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್ 2 ಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿದೆ, ಆದ್ದರಿಂದ ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್ = 3

2 ಮಿನ್‌ಫ್ರೆಕ್‌ಗಿಂತ ಚಿಕ್ಕದಾಗಿದೆ, ಆದ್ದರಿಂದ ಮಿನ್‌ಫ್ರೆಕ್ = 2

  • 3: 2

ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್ 2 ಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿದೆ, ಆದ್ದರಿಂದ ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್ = 3

ಮಿನ್‌ಫ್ರೆಕ್, ಮಿನ್‌ಫ್ರೆಕ್ = 2 ನಲ್ಲಿ ಏನನ್ನೂ ಬದಲಾಯಿಸಲಾಗಿಲ್ಲ

  • 5: 1

ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್ 1 ಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿದೆ, ಆದ್ದರಿಂದ ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್ = 3

1 ಮಿನ್‌ಫ್ರೆಕ್‌ಗಿಂತ ಚಿಕ್ಕದಾಗಿದೆ, ಆದ್ದರಿಂದ ಮಿನ್‌ಫ್ರೆಕ್ = 1

ಸಹ ನೋಡಿ
ಚಿತ್ರಕಲೆ ಬೇಲಿ ಅಲ್ಗಾರಿದಮ್

ಮತ್ತು ನಾವು ಮ್ಯಾಕ್ಸ್‌ಫ್ರೆಕ್-ಮಿನ್‌ಫ್ರೆಕ್ → (3-1) = 2 ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತೇವೆ.

ಕೋಡ್  

ರಚನೆಯಲ್ಲಿ ಅತ್ಯಧಿಕ ಮತ್ತು ಕಡಿಮೆ ಆವರ್ತನಗಳ ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#include<iostream>
#include<unordered_map>

using namespace std;

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

    int maxfreq = 0, minfreq = n;
    for (auto x : freq)
    {
        maxfreq = max(maxfreq, x.second);
        minfreq = min(minfreq, x.second);
    }
    return (maxfreq - minfreq);
}
int main()
{
    int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumDiff(arr, n) << "\n";
    return 0;
}
2

ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಅತ್ಯಧಿಕ ಮತ್ತು ಕನಿಷ್ಠ ಆವರ್ತನಗಳ ನಡುವಿನ ವ್ಯತ್ಯಾಸವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

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

class diffBWHighFLeastF
{
    public static int getMaximumDiff(int arr[], int n)
    {
        HashMap<Integer,Integer> freq = new HashMap<>();
        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);
            }
        }
        int maxfreq = 0, minfreq = n;
        for (Map.Entry<Integer,Integer> x : freq.entrySet())
        {
            maxfreq = Math.max(maxfreq, x.getValue());
            minfreq = Math.min(minfreq, x.getValue());
        }
        return (maxfreq - minfreq);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
        int n = arr.length;
        System.out.println(getMaximumDiff(arr, n));
    }
}
2

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

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

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಇಲ್ಲಿ ನಾವು ರಚನೆಯ ಅಂಶಗಳ ಮೇಲೆ ಅವುಗಳ ಆವರ್ತನಗಳ ಜಾಡನ್ನು ಇಟ್ಟುಕೊಂಡಿದ್ದೇವೆ. ಈ ಎಲ್ಲವು ಒ (ಎನ್) ಸಮಯವನ್ನು ಮಾತ್ರ ಖರ್ಚಾಗುತ್ತದೆ.

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

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಹೆಚ್ಚೆಂದರೆ, ಇವೆಲ್ಲವೂ ವಿಭಿನ್ನವಾಗಿದ್ದರೆ ನಾವು n ಅಂಶಗಳನ್ನು ಸಂಗ್ರಹಿಸಬಹುದು. ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ.