java检查数组是否为零数组

Question

给定一个整数数组，可以在数组中重复选择两个不同的随机项（不一定相邻），然后从每个项中减去1。这样做，一些数组可以转换为全零数组，而一些不能。如何检查数组是否可以转换为零数组？我不知道从哪里开始

例如，给出一个数组：[1,2,1,1]

1. 然后选择1号单位[0,1,1,1]
2. 选择1，1然后减去1个单位->[0,0,0,1]
3. [0,0,0,1]=>；不是零数组

数组的另一个示例可以变成零数组：[1,1,2,2]

1. 选择1，1，然后减去1单位->[0,0,2,2]
2. 选择2，2，然后减去1单位->[0,0,1,1]
3. 选择1，1，然后减去1单位->[0,0,0,0]
   =>[0,0,0,0]是一个零数组

Answer 1

我认为一种算法可以是根据最大和第二（或联合）最大元素来选择一对

// Assuming in.length > 1.
Arrays.sort(in);
while (in[in.length - 1] != 0 && in[in.length - 2] != 0) {
  // Decrement the elements.
   in[in.length-1];
   in[in.length-2];

  // Restore the sorted order
  // (could do this by bubbling the changed elements, done with sort for clarity)
  Arrays.sort(in);
}

if (in[in.length - 1] == 0) {
    System.out.println("Is a zero array");
} else {
    System.out.println("Not a zero array");
}

尝试问题Ideone中的输入：

[1, 2, 1, 1] is not a zero array
[1, 2, 3, 4] is a zero array
[1, 1, 2, 2] is a zero array 

还有一个：

[1, 1, 2] is a zero array (112 -> 011 -> 000)

---

实际上，完全排序是不必要的，因为您只对数组中最后两个位置的值感兴趣

void zero(int[] in) {
  if (in.length > 1) {
    restore(in);

    while (in[in.length - 1] != 0 && in[in.length - 2] != 0) {
       in[in.length-1];
       in[in.length-2];

      restore(in);
    }
  }

  if (in.length == 0 || in[in.length - 1] == 0) {
    System.out.println("Is a zero array");
  } else {
    System.out.println("Not a zero array");
  }
}

void restore(int[] in) {
  // Find the largest element in the array, swap with the last element.
  int largest = largestIndex(in, 0, in.length);
  swap(in, largest, in.length-1);

  // Find the largest element in the array, excluding last element, swap with the second-last element.
  int second = largestIndex(in, 0, in.length-1);
  swap(in, second, in.length-2);
}

void swap(int[] in, int i, int j) {
  int tmp = in[i];
  in[i] = in[j];
  in[j] = tmp;
}

int largestIndex(int[] in, int from, int to) {
  int result = from;
  for (int i = from + 1; i < to; ++i) {
    if (in[i] > in[result]) result = i;
  }
  return result;
}