Untitled
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