js sort and select


  • 0
    Z

    Random Selection Algorithm Based on Quick Sorting

    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    var findKthLargest = function (nums, k) {
        function getKth(nums, start, end, k) {
            let random = Math.floor(Math.random() * (end - start + 1)) + start,
                curIndex = start,
                i = start + 1,
                j = end,
                temp = 0
            
            temp = nums[start]
            nums[start] = nums[random]
            nums[random] = temp
    
            while (true) {
                while ((nums[i] <= nums[curIndex]) && (i < j)) {
                    i++
                }
                while (nums[j] > nums[curIndex]) {
                    j--
                }
    
                if (i >= j) {
                    break
                }
                temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
            }
            temp = nums[start]
            nums[start] = nums[j]
            nums[j] = temp
    
            if (k === j) {
                return nums[j]
            } else if (k > j) {
                return getKth(nums, j + 1, end, k)
            } else {
                return getKth(nums, start, j - 1, k)
            }
        }
    
        return getKth(nums, 0, nums.length - 1, nums.length - k)
    }
    

    The average complexity is O(n)

    Selection Algorithm Based on Quick Sort

    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    var findKthLargest = function (nums, k) {
        function getKth(nums, start, end, k) {
            let curIndex = start,
                i = start + 1,
                j = end,
                temp = 0
    
            while (true) {
                while ((nums[i] <= nums[curIndex]) && (i < j)) {
                    i++
                }
                while (nums[j] > nums[curIndex]) {
                    j--
                }
    
                if (i >= j) {
                    break
                }
                temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
            }
            temp = nums[start]
            nums[start] = nums[j]
            nums[j] = temp
    
            if (k === j) {
                return nums[j]
            } else if (k > j) {
                return getKth(nums, j + 1, end, k)
            } else {
                return getKth(nums, start, j - 1, k)
            }
        }
    
        return getKth(nums, 0, nums.length - 1, nums.length - k)
    }
    

    The average complexity is O(nln(n))

    Use Quick Sort

    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    var findKthLargest = function(nums, k) {
        nums.sort((x, y) => (
            y - x
        ))
        return nums[k - 1]
    }
    

    The complexity is O(nln(n))


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.