මූලද්‍රව්‍ය දෙකක සංඛ්‍යාතය අතර උපරිම වෙනස, වැඩි සංඛ්‍යාතයක් ඇති මූලද්‍රව්‍යයක් ද වැඩි වේ


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇක්සෙන්චර් ඇසොලයිට් ඇමේසන් VMware
අරා හැෂ් වර්ග කිරීම

ඔබට පූර්ණ සංඛ්‍යාවක් ඇතැයි සිතමු අරාව. ලබා දී ඇති අරාවක ඕනෑම විශේෂිත මූලද්‍රව්‍ය දෙකක සංඛ්‍යාතය අතර උපරිම වෙනස සොයා ගැනීමට ගැටළු ප්‍රකාශය අසයි, නමුත් වැඩි සංඛ්‍යාතයක් සහිත මූලද්‍රව්‍යය අනෙක් නිඛිලයට වඩා වැඩි අගයක් තිබිය යුතුය.

උදාහරණයක්

ආදානය:

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

ප්රතිදාන:

2

පැහැදිලි කිරීම:

4 → 3 සංඛ්‍යාතය

2 → 2 සංඛ්‍යාතය

සහ 3 → 1 සංඛ්‍යාතය

4 (3) - 3 (1) = 2 (නිඛිල ද වැඩි හා උපරිම සංඛ්‍යාතය).

ඇල්ගොරිතම

  1. සිතියම අරාව දිග n හි දුර 'යැයි කියනු ලැබේ.
  2. ගණන් කර ගබඩා කරන්න මූලද්‍රව්‍ය සංඛ්‍යාතය සිතියම තුළට ගොස් එකවර අරාවෙහි අගයන් දුර අරාවකට ගබඩා කරන්න.
  3. දුර අරාව වර්ග කරන්න.
  4. අවම වශයෙන් n + 1 ලෙසත් ප්‍රතිදානය 0 ලෙසත් සකසන්න.
  5. අරාව හරහා ගමන් කරන්න, i
    1. ප්‍රතිදානය සහ දුර වටිනාකම [i] සහ අවම අතර වෙනස අතර උපරිමය සොයාගෙන එය ප්‍රතිදානය සඳහා ගබඩා කරන්න.
    2. දුර හා අවම අගය අතර අවම අගය සොයා ගෙන එය අවම වශයෙන් ගබඩා කරන්න.
  6. ප්‍රතිදානය නැවත ලබා දෙන්න.

පැහැදිලි කිරීම

අපට පූර්ණ සංඛ්‍යාවක් ලබා දී ඇති අතර මූලද්‍රව්‍ය දෙකක සංඛ්‍යාතය අතර උපරිම වෙනස සොයා ගැනීමට අපට අවශ්‍ය වන අතර එමඟින් වැඩි සංඛ්‍යාතයක් ඇති මූලද්‍රව්‍යය අවම සංඛ්‍යාතයක් සහිත තවත් පූර්ණ සංඛ්‍යාවකට වඩා වැඩි විය යුතු අතර විශාල සංඛ්‍යාවක් සඳහා අඩු විය යුතුය. අපි පාවිච්චි කරන්නයි යන්නේ හැෂිං සහ වර්ග කිරීම එය කාර්යක්ෂම කේතයක් සෑදීමට අපට උපකාරී වේ. පළමුවෙන්ම, අපි ලබා දී ඇති අරාවෙහි ප්‍රමාණයට සමාන දුරක් සහිත සිතියමක් සහ පූර්ණ සංඛ්‍යා අරාව ප්‍රකාශ කරමු.

අරාවෙහි මූලද්‍රව්‍යයන්ගේ සංඛ්‍යාතය ගබඩා කිරීම සහ ගණනය කිරීම සඳහා අරාව හරහා ගමන් කරන අතරම අපගේ ඇල්ගොරිතමයට අනුව අරාවෙහි වටිනාකම [i] ගබඩා කළ යුතුය. අපි නිමැවුමේ අගය 0 ලෙසත් අවම වශයෙන් n + 1 ලෙසත් සකසමු. මෙම අවම අගය සියලු සංඛ්‍යාත අතර අවම අගය සොයා ගැනීමට අපට උපකාරී වන අතර ප්‍රතිදාන විචල්‍යය තුළ අපි අපගේ උපරිම වෙනස ගබඩා කිරීමට යන්නෙමු. දැන්, අපි අගයන් (දුර අරාව) ගබඩා කරන අරාව වර්ග කළ යුතුය.

අපි දැන් දුර අරාව හරහා ගමන් කරන අතර j අගය දක්වා ගමන් කළ යුතුය. මක්නිසාද යත් පෙර ගමන් වලදී අප දුරින් අගයන් ගබඩා කරන විට අපි j අගය වැඩි කළ නිසා j හි අගය දුර සඳහා උපරිම අගය වේ. ඉහළට ගමන් කිරීමට අරාව. ප්‍රතිදානය සහ සංඛ්‍යාතය සහ අවම අගය අතර වෙනස අතර උපරිම දුර සොයා ගැනීමට අපට අවශ්‍යය. තවද එය ප්‍රතිදානය සඳහා ගබඩා කර තබන්න. තවද දුර අරාව මූලද්‍රව්‍යයේ අවම හා සංඛ්‍යාතය අතර අවම අගය සොයාගෙන එය අවම වශයෙන් ගබඩා කළ යුතුය. අපි සියලු අගයන් දුර අරාවකින් ගමන් කරන තුරු මෙය දිගටම කරගෙන යනු ඇත. අන්තිමේදී, අපට ප්‍රතිදානයේ වඩාත්ම සුදුසු පිළිතුර ඇති අතර අපි එම ප්‍රතිදාන අගය නැවත ලබා දෙන්නෙමු.

ක්රියාත්මක කිරීම

මූලද්‍රව්‍ය දෙකක සංඛ්‍යාතය අතර උපරිම වෙනස සඳහා C ++ වැඩසටහන

#include<unordered_map>
#include<iostream>
#include<algorithm>
using namespace std;

int getMaximumDifference(int arr[], int n)
{
    unordered_map<int, int> freq;

    int distance[n];
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (freq.find(arr[i]) == freq.end())
            distance[j++] = arr[i];

        freq[arr[i]]++;
    }
    sort(distance, distance + j);

    int minimum = n+1;

    int output = 0;
    for (int i=0; i<j; i++)
    {
        int currentFrequency = freq[distance[i]];
        output = max(output, currentFrequency - minimum);
        minimum = min(minimum, currentFrequency);
    }

    return output;
}
int main()
{
    int arr[] = {2,4,4,4,3,2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaximumDifference(arr, n) << endl;
    return 0;
}
2

මූලද්‍රව්‍ය දෙකක සංඛ්‍යාතය අතර උපරිම වෙනස සඳහා ජාවා වැඩසටහන

import java.util.HashMap;
import java.util.Arrays;
class maximumDifferenceFrequency
{
    public static int getMaximumDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> frequency=new HashMap<>();

        int distance[]=new int[n];
        int j = 0;
        for (int i = 0; i < n; i++)
        {
            if (frequency.containsKey(arr[i]))
            {
                frequency.put(arr[i],frequency.get(arr[i])+1);

            }
            else
            {
                frequency.put(arr[i],1);
            }
            distance[j++] = arr[i];
        }
        Arrays.sort(distance);

        int minimum = n+1;

        int output = 0;
        for (int i=0; i<j; i++)
        {
            int currentFrequency = frequency.get(distance[i]);
            output = Math.max(output, currentFrequency - minimum);
            minimum = Math.min(minimum, currentFrequency);
        }

        return output;
    }
    public static void main(String [] args)
    {
        int arr[] = {2,4,4,4,3,2};
        int n = arr.length;

        System.out.println(getMaximumDifference(arr, n));
    }
}
2

මූලද්‍රව්‍ය දෙකක සංඛ්‍යාතය අතර උපරිම වෙනස සඳහා සංකීර්ණතා විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (n ලොග් එන්) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.