问答

当前位置
  • 首页
  • 问答
  • Kth Largest Element 自己实在看不出来哪里错了,求帮看

Kth Largest Element 自己实在看不出来哪里错了,求帮看

  • Ta: 李助教

‘’‘
class Solution:
"""
@param n: An integer
@param nums: An array
@return: the Kth largest element
"""
def kthLargestElement(self, n, nums):
# write your code here
if nums is None or len(nums) == 0:
return -1
if n > len(nums):
return -1
self.partition(nums,0,len(nums) - 1,len(nums) - n)
print(nums)
return nums[-n]

def partition(self,nums,start, end,n):
    #递归的定义
    print(start, end)
    if start >= end:
        return
    left,right = start,end 
    mid = (start + end) // 2 +1
    while left <= right:
        while left <= right and nums[left] < nums[mid]:
            left += 1 
        while left <= right and nums[right] > nums[mid]:
            right -= 1 
        if left <= right:
            nums[left],nums[right] = nums[right], nums[left]
            left += 1 
            right -= 1

    if right >= n:
        self.partition(nums,start,right,n)
    elif left <= n:
        self.partition(nums,left,end, n)

’‘’

1 个回复

2019-09-12 carry

partition函数中,在进入while循环之前,要把nums[mid]记下来,因为在后续的循环中,mid索引位置的元素可能被修改。
改成如下形式:

    def partition(self, nums, start, end, n):
        # 递归的定义
        if start >= end:
            return
        left, right = start, end
        mid = (start + end) // 2 + 1
        pivot = nums[mid]
        while left <= right:
            while left <= right and nums[left] < pivot:
                left += 1
            while left <= right and nums[right] > pivot:
                right -= 1
            if left <= right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1
        print(nums)

        if right >= n:
            self.partition(nums, start, right, n)
        elif left <= n:
            self.partition(nums, left, end, n)

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1