如何将特定值移动到数组末尾而不影响其他元素的顺序？

Question

假设我有一个 [0,7,4,0,0,8,3,0,0,0,5,6] 数组，我必须将所有零放在其他数字之后的最后位置，而不修改它们的顺序。 所以输出数组应该是这样的：[7,4,8,3,5,6,0,0,0,0,0];

我如何使用 Java 8 获得所需的结果输出，任何人都可以建议

我尝试使用以下代码

public class ZeroLast {

    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(0,7,4,0,0,8,3,0,0,0,5,6);
        list.sort(Comparator.reverseOrder());
        System.out.println(list);
    }
}

输出为：[8, 7, 6, 5, 4, 3, 0, 0, 0, 0, 0, 0]

我知道这是因为使用reverseOrder()方法它将使用降序对元素进行排序，但这不是期望的输出。所以我会在这里做任何事情来获取输出，或者您能否提供示例代码逻辑部分来获取结果，谢谢。

Answer 1

您可以在列表上使用排序方法和自定义比较器来执行此操作。

List<Integer> list = Arrays.asList(0,7,4,0,0,8,3,0,0,0,5,6);
list.sort((o1, o2) -> o1 == 0 ? 1 : (o2 == 0 ? -1 : 0));
System.out.println(list);

使用此全 0 必须位于列表末尾，而不修改任何其他顺序。

Answer 2

您可以通过循环来完成此操作，将非零元素移向列表的开头：

int dst = 0;
for (Integer e : list) {
  if (e != 0) {
    list.set(dst++, e);
  }
}

然后将列表的其余部分设置为零：

for (int i = dst; i < list.size(); ++i) {
  list.set(i, 0);
}

或者更简洁地说：

Collections.fill(list.subList(dst, list.size()), 0);

这是一个线性时间操作，除了您尝试排序的列表之外不需要额外的空间。

Answer 3

排序效率不高，也不需要。只需将它们分组，然后重新组合即可。这在线性时间内有效。

• 将它们分组为布尔值所在的

  Map<Boolean, List<Integer>>

  非零时为 false，零时为 true。 （感谢Andy Turner的

  partitioningBy

  建议）。
• via

  collectingAndThen

  通过创建新的

  ArrayList

  处理刚刚创建的映射，首先添加非零列表，然后添加零列表。

List<Integer> list = new ArrayList<>(
        List.of(0, 7, 4, 0, 0, 8, 3, 0, 0, 0, 5, 6));
List<Integer> result = list.stream()
        .collect(Collectors.collectingAndThen(Collectors
                .partitioningBy(i -> i == 0), mp -> {
                    List<Integer> res = new ArrayList<>(
                            mp.get(false));
                    res.addAll(mp.get(true));
                    return res;
                }));
System.out.println(result);

打印

[7, 4, 8, 3, 5, 6, 0, 0, 0, 0, 0, 0]

然后您可以使用此列表或替换原始内容。 这是具有相同结果的更命令式版本。

List<Integer> zeros  = new ArrayList<>();
List<Integer> nonzeros  = new ArrayList<>();
for (int val : list) {
    boolean v = (val == 0) ? zeros.add(val) : nonzeros.add(val);
}
list.clear();
list.addAll(nonzeros);
list.addAll(zeros);

Answer 4

如果你想用数组来做，你可以使用“读”和“写”索引。您沿着数组读取，每当遇到 0 时，就会将其“写入”写入索引。请注意搜索第一次出现的 0，因为这是允许您开始“写入”的位置：

int[] array = {0,7,4,0,0,8,3,0,0,0,5,6};
int writePos = 0;
for (int readPos = 0; readPos < array.length; ++readPos) {
  if (0 != array[readPos]) {
    if (readPos != writePos) {
      array[writePos] = array[readPos];
      array[readPos] = 0; 
    }
    ++writePos;
  }
}
System.out.println(java.util.Arrays.toString(array));