荷兰国旗算法有什么问题？

Question

我试图把一个这样的数组：

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 < 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++; 
     } 
     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 

我的问题是什么？

Answer 1

猜测：

你不应该每一次循环，因为这是应该代表1和未知数之间的隔板增加电流。例如，当你击中前两个时，你最终将换掉另一个2，然后继续前进。 2后来交换0的事实是偶然的。较小和当前之间的元素应始终为1，并且已被打破。

当前++只能在磁带[current]！= 2的情况下完成。磁带[current] = 0时可以这样做，因为您没有更改[更小 - >当前] = 1-only条件。当磁带[current] = 1时移动它是可以的，因为它满足1-only条件。

...但我还没有尝试过。

Answer 2

我要提出一个简单的解决方案:-)

public static int[] sortDNF(int[] tape) { 
    Arrays.sort(tape); 
    return tape; 
} 

至于有什么不对您的解决方案，在当前元素是2，它与附近的列表的末尾元素交换，与它交换的元素可能是而不是是2，但是您正在递增当前并且不再查看此位置。

Answer 3

对于那些还没有研究过这个问题的人来说，排序就足以提供一个解决方案，但它是（或可能）超过必要的。解决DNF问题只需要将所有相似项目一起移动，但不必按任何特定顺序放置不相等的项目。

解决DNF与预期的O（N）复杂性相当容易，其中（最常见形式的）排序具有O（N lg N）复杂性。而不是重新排列输入元素，只要简单地计算具有任何给定值的元素就容易得多，然后打印出每个元素的正确数目。由于不相等元素的顺序无关紧要，因此通常将您的计数存储在散列表中。

Answer 4

的问题是，你对（可能不存在的）值后面的链条回复交换正确跳过1倍的值，尝试在琐碎的情况下，你的算法中：

1 2 0 

2在右侧被交换但当前指数已经超过指数0，最终导致：

1 0 2 

因此，在检查该指数的新值之前，不要增加电流。

Answer 5

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; 
} 

Answer 6

您只需在检查1和检查2时增加电流。当您检查3时，您只需要减小更大。这里的工作解决方案。顺便说一句，这适用于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,2,2,1,2,1,2,1,2,3,1,1,1,1] 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; 
} 

Answer 7

下面是使用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})); 
}