我的荷兰国旗算法出了什么问题？
我试图像这样转一个数组：
0, 1, 2, 2, 1, 0, 1, 0, 0, 1, 2 进入这个：
0 0 0 0 1 1 1 1 2 2 2
这是我的代码：
public static int[] sortDNF(int[] tape) { int smaller = 0; // everything with index bigger is 2 int current = 0; // where we are looking now int tmp; while (current <= bigger) { if (tape[current] == 0) { tmp = tape[smaller]; tape[smaller] = tape[current]; tape[current] = tmp; smaller++; } if (tape[current] == 2) { tmp = tape[bigger]; tape[bigger] = tape[current]; tape[current] = tmp; bigger--; } current++; } return tape; }
这就是它产生的：
0 0 0 1 1 1 1 0 2 2 2
我的问题是什么？
一个猜测：
你不应该每次都通过循环增加电流，因为它应该代表1和未知数之间的分区。 例如，当你击中前2个时，你最终用另外2个交换它然后继续前进。 后来2换成0的事实是偶然的。 较小和当前之间的元素应始终为1并且已被破坏。
current ++应该只在磁带[current]！= 2的情况下完成。 磁带[current] = 0时可以这样做，因为你没有改变[较小 – >当前] =仅1的条件。 当磁带[current] = 1时移动它是可以的，因为它满足了1-only条件。
……但我还没试过。
对于那些没有研究过这个问题的人来说，排序就足以提供一个解决方案，但它是（或可能的）超过必要的。 解决DNF问题只需要将所有类似项目一起移动，但您不必按任何特定顺序放置不相等的项目。
解决具有预期O（N）复杂度的DNF非常容易，其中（大多数正常forms的）排序具有O（N lg N）复杂度。 不是重新排列输入元素，而是简单地计算具有任何给定值的元素，然后打印出正确数量的元素，这样更容易。 由于不相等元素的顺序无关紧要，因此通常将计数存储在哈希表中。
问题是您在链中稍后回复（可能不存在）值以交换错误跳过的1个值，尝试您的算法：
1 2 0
2在正确的位置交换，但当前索引已经超过索引0最终导致：
1 0 2
因此，在检查该索引处的新值之前，请不要增加当前值。
您需要在检查1期间增加电流并检查2.当您检查3时，您只需要减小更大。 这是工作解决方案。 BTW这适用于1-3之间的值数组。 如果您愿意，可以将其更改为0-2。
给定一个随机数组的程序产生如下输出：
原始数组：[1,3,3,3,2,2,2,1,2,2,1,3,3,2,1,1,3]
排序数组：[1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,3,3]
private static int[] sortUsingDutchNationalFlagProblem(int[] array) { System.out.println("Original Array : " + Arrays.toString(array)); int smaller = 0; // everything with index < smaller is 1 int bigger = array.length - 1; // everything with index > bigger is 3 int current = 0; // where we are looking now int tmp; while (current <= bigger) { if (array[current] == 1) { tmp = array[smaller]; array[smaller] = array[current]; array[current] = tmp; smaller++;current++; } if(array[current] == 2) current++; if (array[current] == 3) { tmp = array[bigger]; array[bigger] = array[current]; array[current] = tmp; bigger--; } } System.out.println("Sorted Array : " + Arrays.toString(array)); return array; }
public static int[] sortDNF(int[] tape) { int smaller = 0; // everything with index < smaller is 0 int bigger = tape.length - 1; // everything with index > bigger is 2 int current = 0; // where we are looking now int tmp; while (current <= bigger) { if (tape[current] == 0) { tmp = tape[smaller]; tape[smaller] = tape[current]; tape[current] = tmp; smaller++; } else if (tape[current] == 2) { tmp = tape[bigger]; tape[bigger] = tape[current]; tape[current] = tmp; bigger--; } current++; } return tape; }
这是我使用Java的方法
public static void dutchNationalFlagProblem(int[] input) { int low=0, mid=0, high = input.length -1; while(mid <=high) { switch (input[mid]) { case 0: swap(input, low++, mid++); break; case 1: mid++; break; default : swap(input, mid, high--); break; } } } private static void swap(int[] input, int firstIndex, int secondIndex) { int temp = input[firstIndex]; input[firstIndex] = input[secondIndex]; input[secondIndex] = temp; }
这是相应的测试用例
@Test public void dutchNationalFlagProblemTest() { int[] input = new int[]{0,1,0,2,2,1}; ArrayUtils.dutchNationalFlagProblem(input); assertThat(input, equalTo(new int[]{0,0,1,1,2,2})); }
我打算提出一个更简单的解决方案:-)
public static int[] sortDNF(int[] tape) { Arrays.sort(tape); return tape; }
至于你的解决方案有什么问题，当当前元素为2并且它与列表末尾附近的元素交换时，它与之交换的元素可能不是 2，但是你正在递增当前而不是看这个位置再次。