ٻن عنصرن جي وچ ۾ وڌ ۾ وڌ فرق اهو ته گهڻي عنصر هجڻ وارو عنصر پڻ وڌيڪ آهي


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Accenture قبول ڪريو Amazon VMware
ڪيريو هاش ترتيب ڏيڻ

فرض ڪريو ، توهان وٽ هڪ انوڪار آهي صف. مسئلو بيان ڪيو ويو آهي ته ڏنل ترتيب جي وڌ ۾ وڌ ٻن مختلف عنصرن جي وچ ۾ وڌ ۾ وڌ فرق معلوم ڪري سگهجي ، پر عنصر وڌيڪ عدد سان ٻئي عدد جي لحاظ کان قدر ۾ وڌيڪ هجڻ گهرجي.

مثال

انٽرويو

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

پيداوار:

2

وضاحت:

4 → 3 جي فريڪوئنسي

2 → 2 جي فريڪوئنسي

۽ 3 → 1 جو تعدد

4 (3) - 3 (1) = 2 (انٽيگرز پڻ وڏا ۽ وڌ کان وڌ فریکوئنسي آهن).

الورورٿم

  1. اعلان ڪيو اي نقشي ۽ هڪ صف چوندا آهن فاصلو 'مفاصلي' جي.
  2. ڳڻپ ۽ اسٽور عناصر جو فريڪوئنسي نقشي ۾ ۽ ساڳئي وقت صف جي قدرن کي فاصلو صف ۾ محفوظ ڪريو.
  3. مفاصلي جي ترتيب کي ترتيب ڏيو.
  4. n + 1 تائين گھٽ کي مقرر ڪريو ۽ 0 تي ٻاھر موڪليو.
  5. آرين کي پار ڪيو ، جڏهن ته آئون
    1. ٻاھران وڌ کان وڌ ڳوليو ۽ فاصلو جي وچ ۾ فرق ڳوليو [i] ۽ گھٽ ۾ گھٽ ۽ ان کي محصول ڏانھن اسٽور ڪريو.
    2. گھٽ ۾ گھٽ وچين ۽ فاصلو جي قدر ڳوليو [i] ۽ ان کي گهٽ کان گهٽ ۾ ذخيرو ڪريو.
  6. ٻاھر ٻاھر

وضاحت

اسان کي انٽيگر ڏنو ويو آهي ۽ اسان کي ٻن عنصرن جي فریکوئنسي جي وچ ۾ وڌ ۾ وڌ فرق ڳولڻ جي ضرورت آهي ته جيئن عنصر گهڻي گهڻي فریکوئنسي ٿئي ، پڻ گهٽ ۾ گهٽ تعدد سان ٻئي انٽيگر کان تمام وڏو ۽ وڏي عدد کان گهٽ به هجي. اسان استعمال ٿيڻ وارا آهيون هاشمي ۽ ترتيب ڏيڻ جيڪو اسان کي موثر ڪوڊ ٺاهڻ ۾ مدد ڏيندو. پهريون ، اسان هڪ نقشو ۽ هڪ گڏيل جُڙ جو اعلان ڪيو ويندو جيئن فاصلو ساڳي ماپ سان ڏنل آهي.

جئين اسان جي الگورتھم مطابق صف بندي کي ترتيب ڏيڻ ۽ ڳڻپيوڪرڻ واري آرين جي فریکوئنسي کي پڪ ڪرڻ جي لاءِ اسان کي پڻ صف جي قيمت کي محفوظ ڪرڻ جي ضرورت آهي. اسان ٻاٽي جي قيمت 0 ۽ گهٽ ۾ گهٽ ن + 1 تائين سيٽ ڪنداسين. اهو گهٽ ۾ گهٽ قيمت اسان کي سڀني تعددن ۾ گهٽ ۾ گهٽ ڳولڻ ۾ مدد ڪري ٿي ، ۽ محصول متغير ۾ ، اسان پنهنجو وڌ ۾ وڌ فرق محفوظ ڪرڻ وارا آهيون. ھاڻي ، اسان کي انھن آرين کي ترتيب ڏيڻ جي ضرورت آھي جنھن ۾ اسان ڀينگ کي محفوظ ڪريون (فاصلي جي ترتيب).

اسان ھاڻي مفاصلو ترتيب ڏي سگھون ٿا ۽ اسان کي ج جي قيمت کي جڙڻ جي ضرورت آھي ڇو ته گذريل ٽورورسول ۾ جڏھن اسان فاصلن جا قدر محفوظ ڪري رھيا آھيون اسان ج جي قيمت وڌائي رھيا ھئاسين ، تنھنڪري ج جي قيمت مفاصلو جي وڌ کان وڌ قيمت آھي سفر ڪرڻ تائين. اسان کي ٻاھران سڀ کان وڌيڪ فاصلي ۽ فریکوئنسي ۽ گھٽ قيمت جي وچ ۾ فرق ڳولڻ جي ضرورت آھي. ۽ ان کي آئوٽ اسٽور ڪريو ۽ اسان کي پڻ ضرورت آهي ته گهٽ مفاصلي جي مفاصلي ۽ فاصلي جي آرسي عنصر جي وچ ۾ گهٽ کان گهٽ قدر ۽ ان کي گهٽ ۾ گهٽ اسٽور ڪيو وڃي. اهو جاري رهندو جيستائين جيستائين اسان سڀني قدرن کي مفاهمت جي قطار ۾ نه هرايون. آخر ۾ ، اسان وٽ ٻاولي جو سڀ کان مناسب جواب آھي ۽ اسان ان محصول جي قيمت واپس آڻينداسين.

تي عملدرآمد

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

ٻن عنصرن جي تعدد جي وڌ ۾ وڌ فرق لاءِ پيچيدگي جو تجزيو

وقت جي پيچيدگي

اي (اين لاگ اين) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.

خلائي پيچيدگي

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي.