عام هيش جي فنڪشن کي ترتيب ڏيڻ


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ سيڊنس انڊيا ڪيپسيميني حقيقت جو جائزو ايم UHG آپٽم
ڪيريو هاش ترتيب ڏيڻ

مسئلو “تريول هاش فنڪشن کي استعمال ڪندي ترتيب ڏيڻ” ٻڌائي ٿو ته توهان کي هڪ ڏنو ويو آهي انٽرويو صف. ھڪ صف ٻن منفي ۽ مثبت انگن تي مشتمل ٿي سگھي ٿي. مسئلو بيان ڪتب آڻيندي ترتيب ڏيڻ لاءِ عام هش فنڪشن.

مثال

عام هيش جي فنڪشن کي ترتيب ڏيڻ

arr[] = {5,2,1,3,6}
{1, 2, 3, 5, 6}
arr[] = {-3, -1, 4, 3, -2, 1, 2, 0}
{-3, -2,-1, 0, 1, 2, 3, 4}

وضاحت

سڀ عنصر ٻنهي محصولن ۾ ترتيب ڏنل آهن. ان ڪري محصول صحيح آهن.

الورورٿم

  1. صف جي وڌ کان وڌ ۽ وڌ ۾ وڌ عنصر ڳوليو (گهٽ ۾ گهٽ عنصر پر پورو قدر سان).
  2. وڌ کان وڌ عنصر ۽ گهٽ ۾ گهٽ عنصر جي قطارون ٺاهيو.
  3. هر عنصر جي حساب سان ٻنهي جتن جي ڳڻپ کي وڌاءِ جيڪڏهن اهو 1 کان وڌيڪ يا 0 کان گهٽ آهي ۽ ان کي ترتيب سان ٻنهي اچارن ۾ ترتيب ڏيو.
  4. پرنٽ ڇپايو جيڪو منفي عنصر ڳڻپ آهي ، ڀيڻ ڪڏهن به نه آهي. ساڳيو ڪم مثبت عنصر سان ڪيو.
  5. اسان وٽ هوندي ترتيب ڏنل صف.

وضاحت

اسان کي هڪ ڏنو ويو آهي صف، ان ۾ مثبت ۽ منفي انگ شامل ٿي سگهن ٿا. اسان جو ڪم تريول هش فنڪشن کي استعمال ڪندي ترتيب کي ترتيب ڏيڻ آهي. انهي کي حل ڪرڻ لاءِ اسان ٻن arrays کي هشنگ ۽ شروعاتي استعمال ڪنداسين. وڌ کان وڌ ۽ گهٽ ۾ گهٽ عنصر ڳوليو (گهٽ ۾ گهٽ عنصر مطلق قدر سان). هڪڙو منفي عنصرن لاءِ آهي ۽ ٻيو مثبت عنصرن لاءِ آهي. ٻنهي حڪمن جي ماپ انپٽ جي وڌ کان وڌ عنصر ۽ منفي عنصرن جي برابر هجڻ گهرجي پر مڪمل قدر سان.

اسان ترتيب ڏنل صف کي ڳولينداسين ، ۽ هڪ شرط چڪاس ڪري رهيا آهيون ته جيڪڏهن آرل عنصر 0 کان وڌيڪ آهي ، اسان ان جي وقوع کي 1 ۾ وڌائينداسين هڪ مثبت عنصر واري صف ۾ ۽ جيڪڏهن اهو 0 کان گهٽ آهي ، ان جو مطلب آهي ته نمبر منفي آهي ، هڪ منفي عنصر کي ترتيب ۾ وڌائيندي ان جي واقعن کي وڌائيندو. پيچروئل ​​کان پوء ، اسان کي ٺاهيل هر ترتيب واري عنصر جو شمار اسان جي ٺاهيل ٻنهي حڪمن ۾ آهي.

هاڻي ، اسان کي انهن عنصرن کي ترتيب سان ترتيب ڏيڻ جي ضرورت آهي. تنهن ڪري اسان پهرين منفي عنصر واري صف کي کڻنداسين ، اسان کي گهٽ ۾ گهٽ عنصر کان شروع ڪرڻ جي ضرورت آهي پر منفي نشاني ۽ پرنٽ سان جيترو ڀيرا ٿي سگهي ٿو ۽ ويليو گهٽجي وڃي جيستائين اسان سڀئي منفي قدر ڇپائي ختم نه ڪريون.

ھاڻي کان شروع ڪر ، اسين صف جي سڀني مثبت عنصرن کي پرنٽ ڪري ڇڏينداسين ، جئين ته ڪڏهن به اھو صف ۾ وڌ کان وڌ عنصر تائين ناھي ٿيندو. پر اسان کي يقيني بنائڻو آهي ته اسان صحيح ترتيب کي وڌا وڌ ۽ وڌ ۾ وڌ هڪ صف ۾ پرنٽ ڪيو ۽ پرنٽ منفي عنصر صف ويليو کي منفي نشان سان يا ان کي ضرب ڏيڻ بعد -0 سان. تڪميل کان پوءِ ، اسان ترتيب وار هڪ ڇپيل ڇپيل هئي.

ترڪي هيش فنڪشن استعمال ڪندي ترتيب ڏيڻ

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

using namespace std;

void sortUsingHash(int arr[], int n)
{
    int max = *std::max_element(arr, arr + n);
    int min = abs(*std::min_element(arr, arr + n));

    int positiveNum[max + 1] = { 0 };
    int negativeNum[min + 1] = { 0 };

    for (int i = 0; i < n; i++)
    {
        if (arr[i] >= 0)
            positiveNum[arr[i]] += 1;
        else
            negativeNum[abs(arr[i])] += 1;
    }
    for (int i = min; i > 0; i--)
    {
        if (negativeNum[i])
        {
            for (int j = 0; j < negativeNum[i]; j++)
            {
                cout << (-1) * i << " ";
            }
        }
    }
    for (int i = 0; i <= max; i++)
    {
        if (positiveNum[i])
        {
            for (int j = 0; j < positiveNum[i]; j++)
            {
                cout << i << " ";
            }
        }
    }
}
int main()
{
    int a[] = {7, 5, -4, -3, 2, 4, 1, -2, -1, 0, 6, 3 };

    int n = sizeof(a) / sizeof(a[0]);
    sortUsingHash(a, n);
    return 0;
}
-4 -3 -2 -1 0 1 2 3 4 5 6 7

جاوا ڪوڊ سرانجام ڏيڻ لاءِ نن tو هيش فنڪشن استعمال ڪندي

import java.util.Arrays;
class HashingSorting
{
    public static void sortUsingHash(int arr[], int n)
    {
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Math.abs(Arrays.stream(arr).min().getAsInt());

        int positiveNum[] = new int[max + 1];
        int negativeNum[] = new int[min + 1];

        for (int i = 0; i < n; i++)
        {
            if (arr[i] >= 0)
                positiveNum[arr[i]] += 1;
            else
                negativeNum[Math.abs(arr[i])] += 1;
        }
        for (int i = min; i > 0; i--)
        {
            if (negativeNum[i] > 0)
            {
                for (int j = 0; j < negativeNum[i]; j++)
                {
                    System.out.print((-1)*i+" ");
                }
            }
        }
        for (int i = 0; i <= max; i++)
        {
            if (positiveNum[i] > 0)
            {
                for (int j = 0; j < positiveNum[i]; j++)
                {
                    System.out.print(i+" ");
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int a[] = { 7, 5, -4, -3, 2, 4, 1, -2, -1, 0, 6, 3 };
        int n = a.length;
        sortUsingHash(a, n);
    }
}
-4 -3 -2 -1 0 1 2 3 4 5 6 7

پيچيدگي تجزيي

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

اي (وڌ + منٽ) ، هتي وڌ کان وڌ عنصر گهٽ ۾ گهٽ ۽ عنصر گهٽ آهي. اهڙيءَ طرح وقت جي پيچيدگي ان پٽ جي ماپ تي نه ، پر ان جي عنصر تي منحصر آهي.

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

اي (وڌ + منٽ) ، هتي وڌ کان وڌ عنصر گهٽ ۾ گهٽ ۽ عنصر گهٽ آهي. خلائي پيچيدگي ساڳئي وقت جي پيچيدگي وانگر آهي ، اهو پڻ ان پٽ جي ماپ تي منحصر ناهي. اهو منحصر آهي عناصر جي شدت تي.