荷兰国旗问题.md

荷兰国旗问题

什么是荷兰国旗问题

荷兰国旗

给定一个数组arr, 和一个数num, 
请把小于num的数放在数组的左边, 等于num的数放在数组的中间, 大于num的数放在数组的右边

思路

将数组分为小于区域、等于区域、大于区域三部分
假如数组为 [3, 6, 4, 2, 7] , num为4
less) [3, 6, 4, 2, 7] (more
^      ^               ^
less  curr             more
当curr小于num时, 当前数和小于区域的下一个数交换, curr右移, 小于区域右移
less [3),  6, 4, 2, 7] (more
      ^    ^            ^
      less curr         more
当curr大于num时, 当前数和大于区域的下一个数交换, curr不移, 大于区域左移
less [3),  7, 4, 2, (6] more
      ^    ^         ^
      less curr      more
于是, curr继续比较
less [3),  2, 4, (7, 6] more
      ^    ^      ^
      less curr   more
此时, curr小于num
less [3,  2),  4,     (7, 6] more
          ^    ^      ^
          less curr   more
当curr等于num时, 小于区域不移, 大于区域也不移, curr右移

代码

PHP

<?php

class NetherlandsFlag
{
    public static function partition(&$arr, $L, $R, $num)
    {
        $less = $L - 1;
        $more = $R + 1;
        $curr = $L;

        while ($curr < $more) {
            if ($arr[$curr] < $num) {
                // 当前数和小于区域的下一个数交换, curr右移, 小于区域右移
                self::swap($arr, $curr++, ++$less);
            } elseif ($arr[$curr] > $num) {
                // 当前数和大于区域的下一个数交换, curr不移, 大于区域左移
                self::swap($arr, $curr, --$more);
            } else {
                // 小于区域不移, 大于区域也不移, curr右移
                $curr++;
            }
        }

        // 返回等于区域(如果等于区域不存在则返回一个无效数组)
        return [$less + 1, $more - 1];
    }

    public static function swap(&$arr, $i, $j)
    {
        $tmp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $tmp;
    }
}

// Test
$arr = [3, 6, 4, 2, 7];
// [2, 2]
var_dump(NetherlandsFlag::partition($arr, 0, count($arr) - 1, 4));
// [3, 2, 4, 7, 6]
var_dump($arr);

JAVA

import java.util.Arrays;

public class NetherlandsFlag {
	public static int[] partition(int[] arr, int L, int R, int num) {
		int less = L - 1;
		int more = R + 1;
		int curr = L;
		while (curr < more) {
			if (arr[curr] < num) {
				// 当前数和小于区域的下一个数交换, curr右移, 小于区域右移
				swap(arr, ++less, curr++);
			} else if (arr[curr] > num) {
				// 当前数和大于区域的下一个数交换, curr不移, 大于区域左移
				swap(arr, --more, curr);
			} else {
				// 小于区域不移, 大于区域也不移, curr右移
				curr++;
			}
		}
		
		// 返回等于区域(如果等于区域不存在则返回一个无效数组)
		return new int[] { less + 1, more - 1 };
	}
	
	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}
	
	public static void main(String[] args) {
		int[] arr = {3, 6, 4, 2, 7};
		// [2, 2]
		System.out.println(Arrays.toString(partition(arr, 0, arr.length - 1, 4)));
		// [3, 2, 4, 7, 6]
		System.out.println(Arrays.toString(arr));
	}
}