তুচ্ছ হ্যাশ ফাংশন ব্যবহার করে বাছাই করা


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় ক্যাডেন্স ইন্ডিয়া Capgemini ফ্যাক্সেট ম্যাক ইউএইচজি অপটাম
বিন্যাস কাটা শ্রেণীবিভাজন

"তুচ্ছ হ্যাশ ফাংশন ব্যবহার করে বাছাই করা" সমস্যাটি বলে যে আপনাকে একটি দেওয়া হয়েছে পূর্ণসংখ্যা বিন্যাস। একটি অ্যারেতে নেতিবাচক এবং ধনাত্মক উভয় সংখ্যা থাকতে পারে। সমস্যা বিবরণী ব্যবহার করে অ্যারে বাছাই করতে বলে তুচ্ছ হ্যাশ ফাংশন।

উদাহরণ

তুচ্ছ হ্যাশ ফাংশন ব্যবহার করে বাছাই করা

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. আমরা হবে সাজানো অ্যারে।

ব্যাখ্যা

আমরা একটি দেওয়া হয় বিন্যাস, এটিতে ধনাত্মক এবং negativeণাত্মক পূর্ণসংখ্যা থাকতে পারে। আমাদের কাজ হল তুচ্ছ হ্যাশ ফাংশনটি ব্যবহার করে অ্যারেটিকে সাজানো। এটি সমাধানের জন্য আমরা হ্যাশিং ব্যবহার করব এবং দুটি অ্যারে শুরু করব। সর্বাধিক এবং সর্বনিম্ন উপাদান (পরম মান সহ সর্বনিম্ন উপাদান) সন্ধান করুন। একটি নেতিবাচক উপাদানগুলির জন্য এবং অন্যটি ধনাত্মক উপাদানগুলির জন্য। উভয় অ্যারের আকারের ইনপুটটির সর্বাধিক উপাদান এবং ইনপুটটির নেতিবাচক উপাদানগুলির সমান হওয়া উচিত তবে পরম মান সহ।

আমরা প্রদত্ত অ্যারেটি অতিক্রম করব এবং শর্তটি পরীক্ষা করব যদি অ্যারে উপাদান 0 এর চেয়ে বেশি হয়, তবে আমরা ইতিবাচক উপাদান অ্যারেতে এর উপস্থিতিটি 1 দ্বারা বাড়িয়ে দেব এবং যদি এটি 0 এর চেয়ে কম হয়, এর অর্থ হল সংখ্যাটি নেতিবাচক, আমরা নেতিবাচক উপাদান অ্যারেতে এর উপস্থিতি 1 দ্বারা বাড়ানো হবে। ট্র্যাভারসাল করার পরে, আমরা তৈরি করা উভয় অ্যারেতে প্রতিটি প্রদত্ত অ্যারে উপাদানগুলির সংখ্যা রয়েছে।

এখন, আমাদের সেই উপাদানগুলিকে বাছাই করা পদ্ধতিতে মুদ্রণ করতে হবে। সুতরাং আমরা প্রথমে নেতিবাচক উপাদান অ্যারে নেব, আমাদের ন্যূনতম উপাদানটি থেকে শুরু করতে হবে তবে negativeণাত্মক চিহ্ন সহ এবং যতবার সংঘটিত হবে তার সংখ্যা হিসাবে মুদ্রণ করা উচিত এবং যতক্ষণ না আমরা সমস্ত নেতিবাচক মানগুলি মুদ্রণ না করে অবধি মান হ্রাস করে।

এখন 0 থেকে শুরু করে, আমরা অ্যারের সমস্ত ধনাত্মক উপাদানগুলি মুদ্রণ করব, যতক্ষণ না এটি অ্যারে সর্বাধিক উপাদান পর্যন্ত ঘটে থাকে। তবে আমাদের এটি নিশ্চিত করতে হবে যে আমরা একটি অ্যারেতে সর্বাধিক এবং সর্বনিম্ন হিসাবে সঠিক মানটি পেয়েছি এবং theণাত্মক চিহ্নের সাহায্যে বা এটি -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

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (সর্বোচ্চ + মিনিট), এখানে সর্বোচ্চ হ'ল ইনপুটটিতে সর্বাধিক এবং সর্বনিম্ন উপাদান। সুতরাং সময়ের জটিলতা ইনপুট আকারের উপর নির্ভর করে না তবে এর উপাদানগুলির উপর নির্ভর করে।

স্পেস জটিলতা ity

ও (সর্বোচ্চ + মিনিট), এখানে সর্বোচ্চ হ'ল ইনপুটটিতে সর্বাধিক এবং সর্বনিম্ন উপাদান। স্থান জটিলতাও সময়ের জটিলতার মতো, এটিও ইনপুট আকারের উপর নির্ভর করে না। এটি উপাদানগুলির মাত্রার উপর নির্ভরশীল।