C#-এ ২D অ্যারেতে K-তম স্মলেস্ট এলিমেন্ট বের করা

প্রশ্নের শিরোনামে "২D অ্যারে" বলা হয়েছে কিন্তু উদাহরণে ১D অ্যারে ব্যবহার করা হয়েছে। নিচে দুটি কেসই আলোচনা করা হলো।

কেস ১: ১D অ্যারেতে K-তম স্মলেস্ট (মূল উদাহরণ)

using System;

namespace Program
{
    class Demo
    {
        static void Main(string[] args)
        {
            int[] a = new int[] { 65, 45, 32, 97, 23, 75, 59 };
            int k = 5; // ৫ম স্মলেস্ট
            
            Array.Sort(a); // আরোহী ক্রমে সর্ট
            
            Console.WriteLine("সর্ট করা অ্যারে:");
            foreach (int val in a)
                Console.WriteLine(val);
            
            // K-তম স্মলেস্ট = ইনডেক্স (k-1)
            Console.WriteLine($"\n{k}তম স্মলেস্ট এলিমেন্ট = {a[k - 1]}");
        }
    }
}

আউটপুট

সর্ট করা অ্যারে:
23
32
45
59
65
75
97

৫তম স্মলেস্ট এলিমেন্ট = 65

কেস ২: আসল ২D অ্যারেতে K-তম স্মলেস্ট

using System;
using System.Linq;

public class KthSmallest2D
{
    public static void Main()
    {
        // ২D অ্যারে (ম্যাট্রিক্স)
        int[,] matrix = 
        {
            { 10, 20, 30 },
            { 15, 25, 35 },
            { 27, 29, 37 }
        };
        
        int k = 5;
        
        // ২D অ্যারেকে ১D-এ ফ্ল্যাটেন করুন
        int totalElements = matrix.Length;
        int[] flatArray = new int[totalElements];
        int index = 0;
        
        for (int i = 0; i < matrix.GetLength(0); i++)
        {
            for (int j = 0; j < matrix.GetLength(1); j++)
            {
                flatArray[index++] = matrix[i, j];
            }
        }
        
        // সর্ট করুন
        Array.Sort(flatArray);
        
        Console.WriteLine("ফ্ল্যাটেন করা এবং সর্ট করা অ্যারে:");
        Console.WriteLine(string.Join(", ", flatArray));
        
        if (k >= 1 && k <= flatArray.Length)
        {
            Console.WriteLine($"\n{k}তম স্মলেস্ট এলিমেন্ট = {flatArray[k - 1]}");
        }
        else
        {
            Console.WriteLine("অবৈধ K ভ্যালু!");
        }
    }
}

আউটপুট (২D কেস)

ফ্ল্যাটেন করা এবং সর্ট করা অ্যারে:
10, 15, 20, 25, 27, 29, 30, 35, 37

৫তম স্মলেস্ট এলিমেন্ট = 27

অপ্টিমাইজড পদ্ধতি: QuickSelect (O(n) গড়ে)

পুরো অ্যারে সর্ট না করে শুধু K-তম এলিমেন্ট বের করার জন্য QuickSelect অ্যালগরিদম ব্যবহার করা যায়।

public static int QuickSelect(int[] arr, int k)
{
    // k ১-ভিত্তিক, ইনডেক্স ০-ভিত্তিক
    return QuickSelectHelper(arr, 0, arr.Length - 1, k - 1);
}

private static int QuickSelectHelper(int[] arr, int left, int right, int k)
{
    if (left == right) return arr[left];
    
    int pivotIndex = Partition(arr, left, right);
    
    if (k == pivotIndex)
        return arr[k];
    else if (k < pivotIndex)
        return QuickSelectHelper(arr, left, pivotIndex - 1, k);
    else
        return QuickSelectHelper(arr, pivotIndex + 1, right, k);
}

private static int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right];
    int i = left;
    
    for (int j = left; j < right; j++)
    {
        if (arr[j] <= pivot)
        {
            Swap(arr, i, j);
            i++;
        }
    }
    Swap(arr, i, right);
    return i;
}

private static void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

LINQ ব্যবহার করে সংক্ষিপ্ত সমাধান

using System.Linq;

int kthSmallest = arr.OrderBy(x => x).ElementAt(k - 1);

// ২D অ্যারের জন্য
int kthSmallest2D = matrix.Cast<int>().OrderBy(x => x).ElementAt(k - 1);

পারফরম্যান্স তুলনা