算法：快速选择不返回正确答案

Question

我试图解决“向量 nums 的第 k 大元素是什么”的问题

是一道leetcode题。

下面是全部代码。它应该返回 5。分析代码后，我注意到第二次迭代中的 tail=kth 元素，但是 tail 并不位于最终目的地。只有当我选择最后一个元素作为基准时，事情才是正确的，但为什么呢？无论枢轴选择如何，都应该不起作用？

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int kthLargestElement(vector<int> nums, size_t kth)
    {
        return quickSelect(nums, 0, nums.size()-1, nums.size() - kth);
    }
    int quickSelect(vector<int> nums, size_t left, size_t right, size_t kth)
    {
        size_t tail = left, pointer = left, pivot = (left+right)/2;
        while(pointer <= pivot)
        {
            if(nums[pointer] < nums[pivot])
            {
                std::swap(nums[tail], nums[pointer]);
                tail++; pointer++;
            }
            else
                pointer++;
        }
        
        std::swap(nums[tail], nums[pivot]);
        if(tail > kth)
            return quickSelect(nums, left, tail-1, kth);
        else if(tail < kth)
            return quickSelect(nums, tail+1, right, kth);
        return nums[tail];
    }
};

int main()
{
    Solution s;
    auto test = vector<int>{3,2,1,5,6,4};
    cout<< s.kthLargestElement(test, 2)<< endl;
}

Answer 1

有几个问题：

• 您的循环没有访问主元索引之后的值，但其中一些值也可能小于主元值，因此此错误会影响结果。

• 一旦纠正了前一个点，

  tail

  索引将可能到达

  pivot

  索引，然后交换可以将该枢轴值移动到另一个位置。因此，最终的交换可能不会交换枢轴，而是交换一些其他值。为了避免这种情况，在开始循环之前应将枢轴移到一边，例如移到最右侧。然后我们可以确保在循环之后枢轴没有移动，并且我们可以进行受控交换。

不是问题，但是：

• 通过引用传递向量是个好主意。
• 当您在循环的每次迭代中增加

  pointer

  时，您可以摆脱

  else

  子句，并使用

  for

  循环。

这是对

quickSelect

函数的修正

    // Take the vector by reference:
    int quickSelect(vector<int> &nums, size_t left, size_t right, size_t kth)
    {
        size_t tail = left; 
        // Safeguard pivot value, by moving it to the right side
        std::swap(nums[(left + right) / 2], nums[right]); 
        // Visit ALL values (except pivot)
        for (size_t pointer = left; pointer < right; pointer++) 
        {
            if (nums[pointer] < nums[right]) // Pivot is now at the right
            {
                std::swap(nums[tail], nums[pointer]);
                tail++;
            }
        }

        std::swap(nums[tail], nums[right]); // Now we are sure we swap the pivot
        return tail > kth ? quickSelect(nums, left, tail-1, kth)
             : tail < kth ? quickSelect(nums, tail+1, right, kth)
             : nums[tail];
    }