หา K-th Smallest Element ในอาร์เรย์ 2 มิติ ด้วย C#

ภาพรวม

บทความต้นฉบับใช้โค้ดสำหรับอาร์เรย์ 1 มิติ (ไม่ใช่ 2D) นี่คือวิธีที่ถูกต้องสำหรับทั้งอาร์เรย์ 1D และ 2D

กรณีอาร์เรย์ 1 มิติ (1D Array)

using System;

public class Demo {
    public static void Main() {
        int[] arr = { 65, 45, 32, 97, 23, 75, 59 };
        int k = 5; // หาตัวที่ 5 น้อยที่สุด

        Array.Sort(arr); // เรียงน้อยไปมาก

        Console.WriteLine("Sorted Array: " + string.Join(", ", arr));
        Console.WriteLine($"The {k}th smallest element = {arr[k - 1]}");
    }
}

ผลลัพธ์

Sorted Array: 23, 32, 45, 59, 65, 75, 97
The 5th smallest element = 65

กรณีอาร์เรย์ 2 มิติ (2D Array / Jagged Array)

using System;
using System.Linq;

public class Demo {
    public static void Main() {
        // 2D Array (Rectangular)
        int[,] matrix = {
            { 65, 45, 32 },
            { 97, 23, 75 },
            { 59, 12, 88 }
        };

        int k = 5;

        // Flatten 2D array to 1D
        int[] flat = new int[matrix.Length];
        int idx = 0;
        foreach (var val in matrix) {
            flat[idx++] = val;
        }

        Array.Sort(flat);
        Console.WriteLine($"The {k}th smallest element = {flat[k - 1]}");
    }
}

วิธี LINQ (สั้นที่สุด)

int kthSmallest = matrix.Cast<int>().OrderBy(x => x).ElementAt(k - 1);

ประสิทธิภาพ (Performance)

QuickSelect Implementation (O(n) average)

public static int QuickSelect(int[] arr, int k) {
    return QuickSelect(arr, 0, arr.Length - 1, k - 1);
}

private static int QuickSelect(int[] arr, int left, int right, int k) {
    if (left == right) return arr[left];

    int pivotIndex = new Random().Next(left, right + 1);
    pivotIndex = Partition(arr, left, right, pivotIndex);

    if (k == pivotIndex) return arr[k];
    else if (k < pivotIndex) return QuickSelect(arr, left, pivotIndex - 1, k);
    else return QuickSelect(arr, pivotIndex + 1, right, k);
}

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

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