关于 PartitionArray

最近在研究quick sort, 其中关键步骤需要 PartitionArray. 但是发现网上的两头指针算法似乎是有问题的。。代码如下：

public class Solution {

    public int[] partitionArray(int[] nums, int k) {

        if(nums == null || nums.length == 0){

            return nums;

        }

        int left = 0, right = nums.length - 1;

        while (left <= right) {

            while (left <= right && nums[left] < k) {

                left++;

            }

            while (left <= right && nums[right] >= k) {

                right--;

            }

            if (left <= right) {

                int temp = nums[left];

                nums[left] = nums[right];

                nums[right] = temp;

                left++;

                right--;

            }

        }

        return nums;

    }

}

设计思路很巧妙，从两边找，符合条件往下跳，不符合就等着两边不符合然后交换。。可是如果取的那个刚好是最小值呢并且左边递减右边递增呢？

let nums = (9,8,7,6,3,4,5,8,9); k = 3;

很明显出来的结果不对，网上清一色给的优化方法都是这种两头推进的方法。。是我误解了题目意思还是这种解法真有问题呢？

怎么很明显出来结果不对了。。。

oily 发表于 2017-1-10 04:51
怎么很明显出来结果不对了。。。

987634589, k = 3; 一路都 right-- 出来还是987634589，不是说小于3的要放到3的左边嘛。。

首先，你贴的这段代码的逻辑是“所有>=k的元素要出现在<k的右面”，所以最后的结果忠实地体现了这个前提：在结果9,8,7,6,3,4,5,8,9中，所有>=k的元素（即全部元素）确实是出现在了<k的元素（并不存在）的“右面”。

这个前提并不是太好。因为如果k正好等于min(nums)，那么就可能会出现你所说的这种情况。这种情况下，并没有真正把数组分成两部分。所以如果算法恰好又不能自适应地改变k的话，那么就会一直卡死在这一步，直至耗尽资源。

正确的分割逻辑应该是“所有<=k的元素要出现在>k元素的左边”。这样就算k是最小值，那么也能保证它在partition之后能够位于数组的最左边。这样就还是可以把数组分成[最小值 | 剩余元素] 两个部分。