数据结构|荷兰国旗问题数据结构|算法

问题一：给定一个数组，和一个数num，把小于等于num的数放在数组的左边，大于num的数放在右边。

使用一个指针（代码中为数组下标less）存储数组中小于num的区间，从-1开始。
使用另一个指针来遍历数组（代码中为index），遍历过程中将小于等于num的数归入左边区间，数组下标下移。

func partion(arr []int, target int) { // 将小于等于target的数放到左边，大于target的数放到右边 less := -1 index := 0 for index < len(arr) { if arr[index] <= target { less = less + 1 swap(arr, less, index) } index = index + 1 } }

问题二：（荷兰国旗问题）给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在右边，大于num的数放在左边

分别使用一个指针（less和more）来区分小区间和大区间
使用index来遍历数组，对于小于num的数放到左边，index向右移，对于等于num的数index直接向右移，对于大于num的数先放到右边，index保持不动继续比较

func partionCountry(arr []int, target int) { // 将小于target的数放到左边，等于target的数放在中间，大于target的数放右边 less := -1// 作为小区间 more := len(arr) // 作为大区间 index := 0 for index < more { if arr[index] < target { // 如果数比目标数小 less = less + 1 swap(arr, less, index) index = index + 1 } else if arr[index] > target { // 如果数是比目标数大 more = more - 1 swap(arr, more, index) } else { // 等于 index = index + 1 } } }

下面是上述代码用到的用于交换数组中俩个数的方法代码：

func swap(arr []int, l, r int) { // 交换数组中的俩个数 if l == r || l < 0 || r < 0 || l >= len(arr) || r >= len(arr) { return } arr[l], arr[r] = arr[r], arr[l] }

【数据结构|荷兰国旗问题】