Coding tests are a very important element in modern software development. Companies issue various algorithm problems to evaluate developers’ problem-solving abilities. Today, we will address the problem of finding the Kth smallest number in an array. This problem is a good example to build basic algorithm skills in handling arrays.<\/p>\n
Given an array Return the Kth smallest number from This problem can be easily solved by sorting the array first and then finding the Kth element, but the time complexity may vary depending on the sorting method. Here, we will explore two approaches.<\/p>\n In the code above, we simply sorted the array and found the Kth element. The time complexity of this method is The Quickselect algorithm is a method to find the Kth smallest number in a way similar to Quicksort. This method has an average time complexity of arr<\/code> and an integer k<\/code>, find and return the Kth smallest number in arr<\/code>. The array index starts from 0.<\/p>\nInput<\/h3>\n
\n
arr<\/code>, length between 1 and 100,000.<\/li>\nk<\/code>, between 1 and the length of the array.<\/li>\n<\/ul>\nOutput<\/h3>\n
arr<\/code>.<\/p>\nExample<\/h2>\n
arr = [3, 1, 2, 4, 5], k = 2<\/code>
\nOutput:<\/strong> 2<\/code>
\nExplanation:<\/strong> When the array is sorted in ascending order, it becomes [1, 2, 3, 4, 5], and the 2nd number is 2.\n<\/div>\narr = [7, 10, 4, 3, 20, 15], k = 3<\/code>
\nOutput:<\/strong> 7<\/code>
\nExplanation:<\/strong> When the array is sorted in ascending order, it becomes [3, 4, 7, 10, 15, 20], and the 3rd number is 7.\n<\/div>\nSolution Process<\/h2>\n
Method 1: Sorting the array and finding the Kth number<\/h3>\n
\n
k - 1<\/code> to find the Kth number.<\/li>\n<\/ol>\nJavaScript Code Example<\/h4>\n
function findKthNumber(arr, k) {\n arr.sort((a, b) => a - b); \/\/ Sort the array in ascending order\n return arr[k - 1]; \/\/ Return Kth number\n}\n\n\/\/ Example execution\nconsole.log(findKthNumber([3, 1, 2, 4, 5], 2)); \/\/ 2\nconsole.log(findKthNumber([7, 10, 4, 3, 20, 15], 3)); \/\/ 7\n<\/code><\/pre>\nO(n log n)<\/code>. However, there is a way to find the Kth smallest number without necessarily sorting.<\/p>\nMethod 2: Quickselect Algorithm<\/h3>\n
O(n)<\/code>. This algorithm is performed by setting up a subarray and choosing a pivot.<\/p>\n\n
JavaScript Code Example<\/h4>\n
function quickSelect(arr, left, right, k) {\n if (left === right) {\n return arr[left]; \/\/ If there is only one element in the array\n }\n const pivotIndex = partition(arr, left, right);\n if (k === pivotIndex) {\n return arr[k]; \/\/ Kth number found\n } else if (k < pivotIndex) {\n return quickSelect(arr, left, pivotIndex - 1, k);\n } else {\n return quickSelect(arr, pivotIndex + 1, right, k);\n }\n}\n\nfunction partition(arr, left, right) {\n const pivot = arr[right]; \/\/ Select the last element as the pivot\n let i = left; \n for (let j = left; j < right; j++) {\n if (arr[j] <= pivot) {\n [arr[i], arr[j]] = [arr[j], arr[i]]; \/\/ Swap\n i++;\n }\n }\n [arr[i], arr[right]] = [arr[right], arr[i]]; \/\/ Final position of the pivot\n return i; \/\/ Return the index of the pivot\n}\n\nfunction findKthNumber(arr, k) {\n return quickSelect(arr, 0, arr.length - 1, k - 1); \/\/ Pass K-1 as the argument\n}\n\n\/\/ Example execution\nconsole.log(findKthNumber([3, 1, 2, 4, 5], 2)); \/\/ 2\nconsole.log(findKthNumber([7, 10, 4, 3, 20, 15], 3)); \/\/ 7\n<\/code><\/pre>\n