ایک صف کو کم شکل میں تبدیل کریں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے لنکڈ Snapchat زوم یاہو
لڑی ہیش چھانٹ

مسئلہ یہ بیان

مسئلہ "ایک صف کو کم شکل میں تبدیل کریں" یہ بتاتا ہے کہ آپ کو سائز n کے مختلف عناصر کی ایک صف تیار کی جاتی ہے۔ مسئلے کے بیان میں سرنی کو اس طرح کم کرنے کے لئے کہا گیا ہے کہ نئے نمبروں کو 0 سے لے کر N-1 کی حد میں صف میں رکھا جائے۔ صف کی سب سے چھوٹی تعداد کو 0 سمجھا جانا چاہئے ، اس سے زیادہ 1۔ اور مستقل این -1 نمبر سرنی کا سب سے بڑا عنصر ہے۔

مثال کے طور پر

arr[]={20,10,35,42,8}
2 1 3 4 0

وضاحت: ہمیں 0 کے اندر این -1 کی حد میں صف کی تعداد کو کم شکل میں رکھنا ہے۔ ہم دیکھ سکتے ہیں کہ 8 سب سے چھوٹا ہے ، لہذا یہ 0 ہے 10 اگلا ہے لہذا یہ 1 ، 20 ہے 2 اور اسی طرح ہے۔

 

ایک صف کو کم شکل میں تبدیل کرنے کے لئے الگورتھم

1. Declare a temporary array of size the same as the original array.
2. Copy all the values of the given array into the declared array.
3. Sort that array in which we have copied the value of the original array.
4. Declare a map and set an integer variable ‘val’ to 0.
5. Traverse the array and store the value of the temp array’ element as a key into the map and a val value and increasing the count of ‘val’ by 1 every time.
6. Traverse the original array from 0 to n-1.
  1. Place the value of the map’s key into the array.
7. Print the original array in which we replace the value of the map.

وضاحت

ہم نے انٹیجرز کی ایک صف دی ہے ، ہمیں سرنی کو اس طرح کم کرنا ہے کہ اصل صف میں سے ہر ایک رینج 0 سے لے کر N-1 میں ایک حد لے جائے جس میں رینج سے کوئی قدر ضائع نہ ہو۔ اس کا مطلب یہ ہے کہ اگر ہم نے صف میں 5 نمبر دیئے ہیں تو ہم 0 سے 4 تک تعداد کو اصل صف کے عنصر کی ہر ایک پوزیشن پر شامل کریں گے۔

اس کے ل we ، ہم سائز n کی ایک اضافی صف کا استعمال کریں گے ، ہم کیا کرنے جارہے ہیں ہم اصل سرنی کو اصل صف سے کاپی کریں گے۔ کیونکہ ہم اس پر آپریشن کرنے جارہے ہیں۔ ہم کاپی کی گئی صف کو کم کرتے ہوئے ترتیب میں ترتیب دیں گے۔ کیونکہ ہمیں ہر عنصر کو ایک ایسی تعداد میں کم کرنا ہے جو دیئے گئے حد سے موزوں ہے۔ ہم ایک نقشہ اور متغیر کا اعلان کریں گے 'ویل' 0 پر.

نقشہ عارضی سرنی کی اقدار کو محفوظ کرنے جارہا ہے جسے ہم نے بطور کلید بنایا ہے اور اب عارضی سرنی بھی ترتیب دی گئی ہے تاکہ ہم نمبر o سے n-1 میں رکھ سکیں۔ ہم صف کو عبور کریں گے اور عناصر کو بطور کلید اور رکھیں گے ویل چابی کی قیمت پر. کی قدر ویل ہر بار جب ہم کسی نئی قدر کے ساتھ گذرتے ہیں تو ہم 1 کا اضافہ کریں گے ، لہذا یہ خود بخود 0 سے لے کر n-1 تک ہوتا ہے۔

اصل صف کو عبور کریں اور نقشہ کی تمام اقدار کو اصل صف میں داخل کریں یا ہم کہہ سکتے ہیں کہ ہم اصل صف کو ان نئی اقدار سے بدل دیں گے۔ اصل صف کے ان عناصر کو پرنٹ کریں کیونکہ ہم نے پہلے ہی اسے حد سے بڑھا کر این -0 کردیا ہے۔

ایک صف کو کم شکل میں تبدیل کریں

ضابطے

کسی سرنی کو کم شکل میں تبدیل کرنے کیلئے C ++ کوڈ

#include<iostream>
#include<unordered_map>
#include<algorithm>

using namespace std;

void convert(int arr[], int n)
{
    int temp[n];
    memcpy(temp, arr, n*sizeof(int));

    sort(temp, temp + n);

    unordered_map<int, int> umap;

    int val = 0;
    for (int i = 0; i < n; i++)
        umap[temp[i]] = val++;

    for (int i = 0; i < n; i++)
        arr[i] = umap[arr[i]];
}
void printArr(int arr[], int n)
{
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {20,10,35,42,8};
    int n = sizeof(arr)/sizeof(arr[0]);

    convert(arr, n);
    cout << "Converted Array is : \n";
    printArr(arr, n);
    return 0;
}
Converted Array is :
2 1 3 4 0

 

جاوا کوڈ ایک صف کو کم شکل میں تبدیل کرنے کے لئے

import java.util.HashMap;
import java.util.Arrays;

class ReducedArray
{
    public static void convert(int arr[], int n)
    {
        int temp[] = arr.clone();

        Arrays.sort(temp);

        HashMap<Integer, Integer> umap = new HashMap<>();

        int val = 0;
        for (int i = 0; i < n; i++)
            umap.put(temp[i], val++);


        System.out.println("Converted Array is : ");
        for (int i = 0; i < n; i++)
        {
            arr[i] = umap.get(arr[i]);
            System.out.print(arr[i] + " ");
        }
    }
    public static void main(String[] args)
    {

        int arr[] = {20,10,35,42,8};
        int n = arr.length;
        convert(arr, n);

    }
}
Converted Array is :
2 1 3 4 0

 

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

We ترتیب دیا ہماری ان پٹ سرنی۔ اس لیے O (n لاگ این) کہاں "این" سرنی کا سائز ہے۔

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

چونکہ ہم نے ایک ان پٹ صف کو محفوظ کیا ہے ، لہذا ہم حاصل کرلیں اے (ن) کہاں "این" سرنی کا سائز ہے۔