การเรียงลำดับโดยใช้ฟังก์ชันแฮชเล็กน้อย


ระดับความยาก กลาง
ถามบ่อยใน จังหวะอินเดีย Capgemini ข้อเท็จจริง MAQ UHG Optum
แถว กัญชา การเรียงลำดับ

ปัญหา“ การเรียงลำดับโดยใช้ฟังก์ชันแฮชเล็กน้อย” ระบุว่าคุณได้รับไฟล์ จำนวนเต็ม แถว. อาร์เรย์สามารถมีได้ทั้งจำนวนลบและบวก คำสั่งปัญหาขอให้จัดเรียงอาร์เรย์โดยใช้ ฟังก์ชันแฮชเล็กน้อย

ตัวอย่าง

การเรียงลำดับโดยใช้ฟังก์ชันแฮชเล็กน้อย

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. เราจะมี เรียง แถว

คำอธิบาย

เราได้รับไฟล์ แถวสามารถมีจำนวนเต็มบวกและลบได้ งานของเราคือการจัดเรียงอาร์เรย์โดยใช้ฟังก์ชัน Trivial Hash ในการแก้ปัญหานี้เราจะใช้การแฮชและเริ่มต้นอาร์เรย์สองอาร์เรย์ ค้นหาองค์ประกอบสูงสุดและต่ำสุด (องค์ประกอบต่ำสุดที่มีค่าสัมบูรณ์) หนึ่งคือองค์ประกอบเชิงลบและอีกองค์ประกอบหนึ่งสำหรับองค์ประกอบเชิงบวก ขนาดของอาร์เรย์ทั้งสองควรเท่ากับองค์ประกอบสูงสุดของอินพุตและองค์ประกอบเชิงลบของอินพุต แต่มีค่าสัมบูรณ์

เราจะข้ามอาร์เรย์ที่กำหนดและตรวจสอบเงื่อนไขหากองค์ประกอบอาร์เรย์มีค่ามากกว่า 0 เราจะเพิ่มการเกิดขึ้น 1 ในอาร์เรย์องค์ประกอบเชิงบวกและหากมีค่าน้อยกว่า 0 หมายความว่าจำนวนนั้นเป็นลบเรา จะเพิ่มการเกิดขึ้น 1 ในอาร์เรย์องค์ประกอบเชิงลบ หลังจากการส่งผ่านเรามีจำนวนองค์ประกอบอาร์เรย์ที่กำหนดในอาร์เรย์ทั้งสองที่เราสร้างขึ้น

ตอนนี้เราจำเป็นต้องพิมพ์องค์ประกอบเหล่านั้นในลักษณะที่เรียงลำดับ ดังนั้นเราจะใช้อาร์เรย์องค์ประกอบเชิงลบเป็นอันดับแรกเราต้องเริ่มจากองค์ประกอบขั้นต่ำ แต่ด้วยเครื่องหมายลบและพิมพ์ตามจำนวนครั้งที่เกิดขึ้นและลดค่าลงจนกว่าเราจะพิมพ์ค่าลบทั้งหมดเสร็จสิ้น

ตอนนี้เริ่มจาก 0 เราจะพิมพ์องค์ประกอบเชิงบวกทั้งหมดของอาร์เรย์โดยไม่มีจำนวนครั้งที่เกิดขึ้นจนถึงองค์ประกอบสูงสุดในอาร์เรย์ แต่เราต้องแน่ใจว่าเราพบค่าที่ถูกต้องเป็นค่าสูงสุดและต่ำสุดในอาร์เรย์และพิมพ์ค่าอาร์เรย์องค์ประกอบเชิงลบด้วยเครื่องหมายลบหรือหลังจากคูณด้วย -1 หลังจากเสร็จสิ้นเราได้พิมพ์อาร์เรย์ที่เรียงลำดับ

รหัส C ++ เพื่อดำเนินการเรียงลำดับโดยใช้ฟังก์ชันแฮชเล็กน้อย

#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

โค้ด Java เพื่อดำเนินการเรียงลำดับโดยใช้ฟังก์ชันแฮชเล็กน้อย

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

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (สูงสุด + นาที) ที่นี่ max คือองค์ประกอบสูงสุดและต่ำสุดในอินพุต ดังนั้นความซับซ้อนของเวลาจึงไม่ขึ้นอยู่กับขนาดของอินพุต แต่ขึ้นอยู่กับองค์ประกอบ

ความซับซ้อนของอวกาศ

O (สูงสุด + นาที) ที่นี่ max คือองค์ประกอบสูงสุดและต่ำสุดในอินพุต ความซับซ้อนของพื้นที่ก็เหมือนกับความซับซ้อนของเวลา แต่ก็ไม่ได้ขึ้นอยู่กับขนาดของอินพุต ขึ้นอยู่กับขนาดขององค์ประกอบ