Algorithm problems in coding tests often evaluate theoretical knowledge and practical problem-solving skills that are frequently used in actual work. In this article, we will discuss the problem of finding the Kth number in an array. This problem requires techniques for sorting an array and extracting values from specific indices.
Problem Description
Given an integer array array and an integer k, write a function that returns the Kth number after sorting array in ascending order. The Kth number uses 1-based indexing.
Input
array: An array containing integers, e.g., [3, 1, 2, 4, 5]k: A positive integer to find the Kth number in the array
Output
Output the Kth number after sorting array. If K is greater than the length of the array, return -1.
Example
Input:
array = [3, 5, 2, 1, 4]
k = 3
Output:
3
Solution
To solve this problem, we can proceed with the following steps:
- Sort the given input array.
- Reference the Kth number from the sorted array and return it.
Step-by-step Solution
Step 1: Sorting the Array
There are several ways to sort an array. Common sorting algorithms include Quick Sort, Merge Sort, and Insertion Sort. However, using the built-in sorting function provided by Swift allows for convenient sorting.
Step 2: Finding the Kth Number
To find the Kth number in the sorted array, we return the value at the K-1 index. If K exceeds the length of the array, we should return -1.
Swift Code Implementation
func findKthNumber(array: [Int], k: Int) -> Int {
let sortedArray = array.sorted()
guard k > 0 && k <= sortedArray.count else {
return -1
}
return sortedArray[k - 1]
}
// Test
let array = [3, 5, 2, 1, 4]
let k = 3
print(findKthNumber(array: array, k: k)) // Output: 3
Complexity Analysis
Time Complexity: The time complexity for sorting is O(n log n), where n is the length of the array.
Space Complexity: The additional space complexity for sorting is O(n).
Conclusion
Through this problem, we learned about sorting arrays and accessing specific indices. This foundational thinking can be applied to other algorithm problems as well.
If you want more problem-solving and algorithm tutorials, please continue to visit the blog. Thank you!