三路分区

Question

三向划分问题，使用左、中、右指针在 lowVal 和 highVal 之间交换小于 lowVal 的值以及大于 highVal 的值。对于我现在正在经历的测试用例之一，它无法正常工作。问题是我不确定算法或测试用例。

arr[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32}
lowVal = 1 and highVal = 3

1. 所有小于 lowRange 的元素都排在前面。 2) 接下来是 lowVal 到 highRange 范围内的所有元素。 3）所有大于highRange的元素都出现在最后。

输出应该是：

[1, 1, 2, 3, 4, 54, 20, 87, 98, 20, 5, 32, 14]

但是三指针荷兰国旗算法方式给出了输出：

[1, 1, 3, 2, 4, 54, 20, 87, 98, 20, 5, 32, 14]

您可以在输出中看到 2 在 3 之后，我认为这是错误的，因为它应该在 1 和 3 之间。请让我知道您对此的想法。我已附上代码供参考。

def threeway(self, nums, lowVal, highVal):
    l, m, r = 0, 0, len(nums) - 1
    
    while m <= r:
        if nums[m] < lowVal:
            nums[m], nums[l] = nums[l], nums[m]
            l += 1
            m += 1
        elif nums[m] > highVal:
            nums[m], nums[r] = nums[r], nums[m]
            r -= 1
        else:
            m += 1
            
    return nums

Answer 1

这个函数是分区数组，所以没关系，也许参考实现在比较中存在差异，比如

>

而不是

>=

或者 while 从头到尾，无论哪种方式它都会分裂，所以你对正确的分块感兴趣，这很好排序

这会产生所需的输出

def threeway(nums, lowVal, highVal):
    l, m, r = 0, len(nums) - 1, len(nums) - 1
    
    while m >= l:
        if nums[m] < lowVal:
            nums[m], nums[l] = nums[l], nums[m]
            l += 1
        elif nums[m] > highVal:
            nums[m], nums[r] = nums[r], nums[m]
            r -= 1
        m -= 1
            
    return nums