Untitled

 avatar
unknown
plain_text
14 days ago
2.5 kB
2
Indexable
import java.util.*;

public class KthLargestNumber {
    public String kthLargestNumber(String[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }

    private String quickSelect(String[] nums, int left, int right, int targetIndex) {
        if (left == right) {
            return nums[left];
        }

        // Step 1: Choose a pivot and partition the array
        int pivotIndex = partition(nums, left, right);

        // Step 2: Check if the pivot is at the target index
        if (pivotIndex == targetIndex) {
            return nums[pivotIndex];
        } else if (pivotIndex < targetIndex) {
            // Search the right part
            return quickSelect(nums, pivotIndex + 1, right, targetIndex);
        } else {
            // Search the left part
            return quickSelect(nums, left, pivotIndex - 1, targetIndex);
        }
    }

    private int partition(String[] nums, int left, int right) {
        String pivot = nums[right]; // Choose the last element as the pivot
        int i = left;

        for (int j = left; j < right; j++) {
            // Compare nums[j] and pivot
            if (compare(nums[j], pivot) > 0) {
                // Swap nums[i] and nums[j]
                swap(nums, i, j);
                i++;
            }
        }

        // Place the pivot in its correct position
        swap(nums, i, right);
        return i;
    }

    private void swap(String[] nums, int i, int j) {
        String temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private int compare(String a, String b) {
        // Compare by length
        if (a.length() != b.length()) {
            return Integer.compare(a.length(), b.length());
        }
        // Compare lexicographically if lengths are equal
        return a.compareTo(b);
    }

    public static void main(String[] args) {
        KthLargestNumber solution = new KthLargestNumber();

        // Example 1
        String[] nums1 = {"3", "6", "7", "10"};
        int k1 = 4;
        System.out.println(solution.kthLargestNumber(nums1, k1)); // Output: "3"

        // Example 2
        String[] nums2 = {"2", "21", "12", "1"};
        int k2 = 3;
        System.out.println(solution.kthLargestNumber(nums2, k2)); // Output: "2"

        // Example 3
        String[] nums3 = {"0", "0"};
        int k3 = 2;
        System.out.println(solution.kthLargestNumber(nums3, k3)); // Output: "0"
    }
}
Leave a Comment