LeetCode 1387. Sort Integers by The Power Value

剛從南湖群峰下山,原本受了現在好像又胖回去了(哭
const steps = (x) => {
let result = 0
while (x !== 1) {
x = x%2 ? 3*x + 1 : x/2
result ++
}
return result
}
const comparator = (a, b) => {
return a[1] === b[1] ? a[0] - b[0] : a[1] - b[1]
}
const partition = (low, high, Arr) => {
let pivot = Arr[high] // make the pivot as the last element
let slow = low
for (let fast = low; fast < high; fast++) {
if (comparator(Arr[fast], pivot) < 0) {
[Arr[slow], Arr[fast]] = [Arr[fast], Arr[slow]]
slow ++
}
}
[Arr[slow], Arr[high]] = [Arr[high], Arr[slow]]
return slow
}
const quickSelect = (Arr,k) => {
let low = 0
let high = Arr.length -1
while (low < high) { // using quick sort
let indexOfPivot = partition(low, high, Arr)
if (indexOfPivot < k) low = indexOfPivot + 1
else if (indexOfPivot > k) high = indexOfPivot - 1
else break //case k
}
return Arr[k]
}
const getKth = (lo, hi, k) => {
if (lo === hi) return lo
let poweredArray = []
for (let i = lo; i < hi+1; i++) {
poweredArray.push([i, steps(i)])
}
return quickSelect(poweredArray, k-1)[0]
};

參考:Comparison Sort: Quick Sort(快速排序法)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
黃韋智

自學寫程式,目前爲 React 前端工程師。熱愛旅遊,將近 30 個國家,足跡遍佈亞洲與歐洲。生命與街舞已經離不開,歡迎訂閱 Youtube 頻道:https://www.youtube.com/channel/UCEU-bEDl7R-iGyLVZFae33g