Skip to content

Instantly share code, notes, and snippets.

@alimir1
Created January 8, 2017 21:09
Show Gist options
  • Save alimir1/b04e0e97e531ca21020eafed012d4106 to your computer and use it in GitHub Desktop.
Save alimir1/b04e0e97e531ca21020eafed012d4106 to your computer and use it in GitHub Desktop.
Find Kth smallest element in array
func findSmallestKth(_ array: [Int], _ k: Int) -> Int {
let pivot = array.first!
let arraySmallerThanPivot = array.dropFirst().filter {$0 < pivot}
let arrayLargerThanPivot = array.dropFirst().filter { $0 > pivot }
let newArray = arraySmallerThanPivot + [Int(pivot)] + arrayLargerThanPivot
let positionOfPivot = array.count > 1 ? arraySmallerThanPivot.count : 0
if k-1 == positionOfPivot {
return newArray[positionOfPivot]
} else if k-1 > positionOfPivot {
return findSmallestKth(arrayLargerThanPivot, k-1-positionOfPivot)
} else {
return findSmallestKth(arraySmallerThanPivot, k)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment