ਛੋਟੀ ਹੈਸ਼ ਫੰਕਸ਼ਨ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਛਾਂਟਣਾ


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਕੈਡੈਂਸ ਇੰਡੀਆ ਕੈਪਜੀਨੀ ਤੱਥ ਮੈਕ 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 ਤੋਂ ਵੱਧ ਹੈ ਜਾਂ 0 ਤੋਂ ਘੱਟ ਹੈ ਅਤੇ ਇਸ ਨੂੰ ਕ੍ਰਮਵਾਰ ਦੋਵੇਂ ਐਰੇ ਵਿਚ ਸਟੋਰ ਕਰੋ.
  4. ਐਰੇ ਨੂੰ ਪ੍ਰਿੰਟ ਕਰੋ ਜਿਸ ਵਿੱਚ ਇੱਕ ਨਕਾਰਾਤਮਕ ਤੱਤ ਦੀ ਗਿਣਤੀ ਹੁੰਦੀ ਹੈ, ਜਿੰਨੀ ਵਾਰ ਹੁੰਦੀ ਹੈ. ਸਕਾਰਾਤਮਕ ਤੱਤ ਨਾਲ ਉਹੀ ਕੰਮ ਕਰੋ.
  5. ਸਾਡੇ ਕੋਲ ਹੋਵੇਗਾ ਕ੍ਰਮਬੱਧ ਐਰੇ.

ਕਥਾ

ਸਾਨੂੰ ਇੱਕ ਦਿੱਤਾ ਗਿਆ ਹੈ ਐਰੇ, ਇਸ ਵਿੱਚ ਸਕਾਰਾਤਮਕ ਅਤੇ ਨਕਾਰਾਤਮਕ ਪੂਰਨ ਅੰਕ ਸ਼ਾਮਲ ਹੋ ਸਕਦੇ ਹਨ. ਸਾਡਾ ਕੰਮ ਟ੍ਰਿਵੀਅਲ ਹੈਸ਼ ਫੰਕਸ਼ਨ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਐਰੇ ਨੂੰ ਸੌਰਟ ਕਰਨਾ ਹੈ. ਇਸ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਅਸੀਂ ਹੈਸ਼ਿੰਗ ਦੀ ਵਰਤੋਂ ਕਰਾਂਗੇ ਅਤੇ ਦੋ ਐਰੇ ਅਰੰਭ ਕਰਾਂਗੇ. ਵੱਧ ਤੋਂ ਵੱਧ ਅਤੇ ਘੱਟੋ ਘੱਟ ਤੱਤ (ਸੰਪੂਰਨ ਮੁੱਲ ਵਾਲਾ ਘੱਟੋ ਘੱਟ ਤੱਤ) ਲੱਭੋ. ਇਕ ਨਕਾਰਾਤਮਕ ਤੱਤਾਂ ਲਈ ਹੈ ਅਤੇ ਦੂਜਾ ਸਕਾਰਾਤਮਕ ਤੱਤਾਂ ਲਈ. ਦੋਵੇਂ ਐਰੇ ਦਾ ਆਕਾਰ ਇਨਪੁਟ ਦੇ ਵੱਧ ਤੱਤ ਅਤੇ ਇਨਪੁਟ ਦੇ ਨਕਾਰਾਤਮਕ ਤੱਤ ਦੇ ਬਰਾਬਰ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ ਪਰ ਸੰਪੂਰਨ ਮੁੱਲ ਦੇ ਨਾਲ.

ਅਸੀਂ ਦਿੱਤੀ ਗਈ ਐਰੇ ਨੂੰ ਟ੍ਰਾੱਰ ਕਰਾਂਗੇ, ਅਤੇ ਇਕ ਸ਼ਰਤ ਦੀ ਜਾਂਚ ਕਰ ਰਹੇ ਹਾਂ ਜੇ ਕੋਈ ਐਰੇ ਐਲੀਮੈਂਟ 0 ਤੋਂ ਵੱਧ ਹੈ, ਤਾਂ ਅਸੀਂ ਇਸ ਦੀ ਮੌਜੂਦਗੀ ਨੂੰ ਸਕਾਰਾਤਮਕ ਐਲੀਮੈਂਟ ਐਰੇ ਵਿਚ 1 ਨਾਲ ਵਧਾਵਾਂਗੇ ਅਤੇ ਜੇ ਇਹ 0 ਤੋਂ ਘੱਟ ਹੈ, ਤਾਂ ਇਸਦਾ ਅਰਥ ਹੈ ਕਿ ਸੰਖਿਆ ਨਕਾਰਾਤਮਕ ਹੈ, ਅਸੀਂ ਇੱਕ ਨਕਾਰਾਤਮਕ ਤੱਤ ਐਰੇ ਵਿੱਚ ਆਪਣੀ ਮੌਜੂਦਗੀ ਨੂੰ 1 ਨਾਲ ਵਧਾਏਗਾ. ਟ੍ਰਾਵਰਸਾਲ ਤੋਂ ਬਾਅਦ, ਸਾਡੇ ਦੁਆਰਾ ਬਣਾਏ ਗਏ ਦੋਵੇਂ ਐਰੇ ਵਿਚ ਸਾਡੇ ਦਿੱਤੇ ਗਏ ਐਰੇ ਐਲੀਮੈਂਟ ਦੀ ਗਿਣਤੀ ਹੈ.

ਹੁਣ, ਸਾਨੂੰ ਉਨ੍ਹਾਂ ਤੱਤਾਂ ਨੂੰ ਛਾਂਟਵੇਂ printੰਗ ਨਾਲ ਪ੍ਰਿੰਟ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ. ਇਸ ਲਈ ਅਸੀਂ ਪਹਿਲਾਂ ਨਕਾਰਾਤਮਕ ਤੱਤ ਐਰੇ ਲਵਾਂਗੇ, ਸਾਨੂੰ ਘੱਟੋ ਘੱਟ ਤੱਤ ਤੋਂ ਸ਼ੁਰੂ ਕਰਨ ਦੀ ਜ਼ਰੂਰਤ ਹੈ ਪਰ ਨਕਾਰਾਤਮਕ ਸੰਕੇਤ ਦੇ ਨਾਲ ਜਿੰਨੀ ਵਾਰ ਹੁੰਦਾ ਹੈ ਦੇ ਰੂਪ ਵਿੱਚ ਪ੍ਰਿੰਟ ਕਰੋ ਅਤੇ ਮੁੱਲ ਘਟਾਉਂਦੇ ਹੋਏ ਜਦੋਂ ਤੱਕ ਅਸੀਂ ਸਾਰੇ ਨਕਾਰਾਤਮਕ ਮੁੱਲਾਂ ਨੂੰ ਛਾਪਣ ਤੋਂ ਖਤਮ ਨਹੀਂ ਕਰਦੇ.

ਹੁਣ 0 ਤੋਂ ਸ਼ੁਰੂ ਕਰਦੇ ਹੋਏ, ਅਸੀਂ ਐਰੇ ਦੇ ਸਾਰੇ ਸਕਾਰਾਤਮਕ ਤੱਤ ਪ੍ਰਿੰਟ ਕਰਾਂਗੇ, ਜਿਵੇਂ ਕਿ ਐਰੇ ਦੇ ਵੱਧ ਤੋਂ ਵੱਧ ਤੱਤ ਤੱਕ ਨਹੀਂ ਹੁੰਦਾ. ਪਰ ਸਾਨੂੰ ਇਹ ਨਿਸ਼ਚਤ ਕਰਨਾ ਹੈ ਕਿ ਅਸੀਂ ਇੱਕ ਐਰੇ ਵਿਚ ਵੱਧ ਤੋਂ ਵੱਧ ਅਤੇ ਘੱਟੋ ਘੱਟ ਦੇ ਤੌਰ ਤੇ ਸਹੀ ਮੁੱਲ ਪਾਇਆ ਹੈ ਅਤੇ ਨਕਾਰਾਤਮਕ ਤੱਤ ਐਰੇ ਮੁੱਲ ਨੂੰ ਨਕਾਰਾਤਮਕ ਸੰਕੇਤ ਨਾਲ ਜਾਂ ਇਸ ਨੂੰ -1 ਨਾਲ ਗੁਣਾ ਕਰਨ ਤੋਂ ਬਾਅਦ ਛਾਪਿਆ ਹੈ. ਮੁਕੰਮਲ ਹੋਣ ਤੋਂ ਬਾਅਦ, ਅਸੀਂ ਇੱਕ ਕ੍ਰਮਬੱਧ ਐਰੇ ਪ੍ਰਿੰਟ ਕੀਤਾ ਸੀ.

ਮਾਮੂਲੀ ਹੈਸ਼ ਫੰਕਸ਼ਨ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਛਾਂਟਣ ਲਈ ਸੀ ++ ਕੋਡ

#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

ਮਾਮੂਲੀ ਹੈਸ਼ ਫੰਕਸ਼ਨ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਛਾਂਟੀ ਕਰਨ ਲਈ ਜਾਵਾ ਕੋਡ

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

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਅਧਿਕਤਮ + ਮਿੰਟ), ਇੱਥੇ ਇਨਪੁਟ ਵਿਚ ਅਧਿਕਤਮ ਅਤੇ ਘੱਟੋ ਘੱਟ ਤੱਤ ਹੈ. ਇਸ ਤਰ੍ਹਾਂ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਇੰਪੁੱਟ ਦੇ ਅਕਾਰ 'ਤੇ ਨਿਰਭਰ ਨਹੀਂ ਕਰਦੀ ਬਲਕਿ ਇਸਦੇ ਤੱਤ' ਤੇ ਨਿਰਭਰ ਕਰਦੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਅਧਿਕਤਮ + ਮਿੰਟ), ਇੱਥੇ ਇਨਪੁਟ ਵਿਚ ਅਧਿਕਤਮ ਅਤੇ ਘੱਟੋ ਘੱਟ ਤੱਤ ਹੈ. ਪੁਲਾੜ ਦੀ ਜਟਿਲਤਾ ਵੀ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਵਾਂਗ ਹੀ ਹੈ, ਇਹ ਇੰਪੁੱਟ ਦੇ ਆਕਾਰ 'ਤੇ ਵੀ ਨਿਰਭਰ ਨਹੀਂ ਕਰਦੀ. ਇਹ ਤੱਤ ਦੀ ਵਿਸ਼ਾਲਤਾ 'ਤੇ ਨਿਰਭਰ ਕਰਦਾ ਹੈ.