Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit31e8a7d

Browse files
t3chkidt3chkid
t3chkid
authored and
t3chkid
committed
add solution that uses "Quick Select" algorithm for "215. Kth Largest Element in an Array" in Kotlin
1 parent3cfb9a5 commit31e8a7d

File tree

1 file changed

+38
-0
lines changed

1 file changed

+38
-0
lines changed

‎kotlin/215-Kth-Largest-Element-In-Array.kt

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -11,4 +11,42 @@ class Solution {
1111

1212
return heap.peek()
1313
}
14+
15+
// O(n) average time complexity - Quick Select algorithm
16+
funfindKthLargestRecursive(nums:IntArray,k:Int):Int= quickSelect(
17+
array= nums,
18+
startIndex=0,
19+
endIndex= nums.lastIndex,
20+
k= k
21+
)
22+
23+
privatefunquickSelect(
24+
array:IntArray,
25+
startIndex:Int,
26+
endIndex:Int,
27+
k:Int,
28+
):Int {
29+
// find a valid position for pivot such that all values that
30+
// appear before the pivot are lower than the value of pivot,
31+
// and, all values that appear after the pivot are greater
32+
// than the pivot.
33+
@Suppress("UnnecessaryVariable")val pivotIndex= endIndex
34+
var validIndexForPivot= startIndex
35+
for (iin startIndex until endIndex) {
36+
if (array[i]< array[pivotIndex]) {
37+
val temp= array[i]
38+
array[i]= array[validIndexForPivot]
39+
array[validIndexForPivot]= temp
40+
validIndexForPivot++
41+
}
42+
}
43+
// put pivot element in it's sorted position
44+
val temp= array[validIndexForPivot]
45+
array[validIndexForPivot]= array[pivotIndex]
46+
array[pivotIndex]= temp
47+
48+
returnif (validIndexForPivot== (array.size- k)) array[validIndexForPivot]
49+
elseif (validIndexForPivot> array.size- k) quickSelect(array, startIndex, validIndexForPivot-1, k)
50+
else quickSelect(array, validIndexForPivot+1, endIndex, k)
51+
}
1452
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp