java如何修改此代码，使其时间复杂度为o（logn）或o（n），而不是o（n^2）

Question

如何在o（n）或o（logn）中解决此问题

下课后，n组学生走出教室，决定去Polycarpus庆祝他的生日。我们知道第i组由si朋友（1）组成 ≤ 硅 ≤ 4） ，他们想一起去Polycarpus。他们决定乘出租车去那里。每辆车最多能载四名乘客。如果每个小组的所有成员都乘坐同一辆出租车（但一辆出租车可以乘坐多个小组），那么孩子们至少需要多少辆车？ 以下是我的方法，但在o（n^2）中

import java.util.*;

public class taxi {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {
      int cars = 0;
      int groups = sc.nextInt();
      int[] a = new int[groups];
      for (int i = 0; i < a.length; i++) {
        a[i] = sc.nextInt();
      }
      Arrays.sort(a);
      for (int i = a.length - 1; i > 0; i--) {

        if (a[i] == 4) {
          cars = cars + 1;
        } else {
          if (a[i] == 0) {
            break;
          } else {
            int y = 4 - a[i];
            for (int j = i - 1; j >= 0; j--) {
              if (y - a[j] == 0) {
                a[j] = 0;
                break;
              }
              if (y - a[j] > 0) {
                y = y - a[j];
                a[j] = 0;
              }
            }
            cars = cars + 1;
            Arrays.sort(a);
          }
        }
      }
      if (a[0] != 0) {
        cars++;
      }
      System.out.println(cars);
      cars = 0;
    }
  }
}

Answer 1

与芭丝谢芭建议的解决方案类似，但基于每种大小的组数，而不是缓存：

在组列表上迭代一次，计算每个大小的组有多少个。这需要O(n)时间，并提供以下计数器：

int size1 = ...
int size2 = ...
int size3 = ...
int size4 = ...

现在根据这些计数器计算汽车数量（此计算需要O(1)）：

int carsCount = size4; // add full cars (groups of 4)
carsCount += size3; // each group of 3 requires a separate car
carsCount += size2/2; // pairs of groups of 2
size1 -= size3; // group as many groups of 1 with groups of 3 as possible
boolean odd2s = (size2 % 2) == 1;
if (odd2s) {
    carsCount++; // add a car for the odd group of 2
}
if (size1 > 0) {
    if (odd2s) {
        size1 -= 2; // two groups of 1 can be paired with the odd group of 2
    }
}
if (size1 > 0) {
    carsCount += (size1 + 3) / 4; // any remaining groups of 1 are grouped in groups of 4
}

Answer 2

你永远不会达到O（logn），因为你必须检查每个组

您可以通过一次遍历组集和一个缓存来实现：so O（N）

计算每组的大小

1. 如果是4，那就加一辆出租车
2. 如果是3，则尝试与缓存的1配对，如果不是，则缓存该组
3. 如果是1，则尝试与缓存的3配对，如果不是，则缓存该组
4. 如果是2，则尝试与缓存的2配对，如果不是，则缓存该组

检查缓存。将任意一组2与一组或多组1配对。然后将剩余的1组配对

Answer 3

只有4种分组大小：1、2、3或4

初始化每个大小的计数数组，遍历组大小数组，增加组大小对应的数组元素

// Count the number of groups of each size.
int[] counts = new int[5];  // 1 more, just to use 1-based indexing.
for (int e : a) {
  ++counts[e];
}

也就是O(n)

然后，像这样通过：

int numTaxis =   counts[4];      // 1 taxi for each 4-sized group.
               + counts[3];      // 1 taxi for each 3-sized group.
               + counts[2] / 2;  // 1 taxi for each pair of 2-sized groups.

// But you can put a 1-sized group in each 3-sized group's taxi.
int unmatched1s = Math.max(0, counts[1] - counts[3]);

// You require ceil(unmatched1s / 4) taxis for the 1-sized groups -
// - but increase by 1 to handle the possibility of unpaired 2-sized group.
numTaxis += (unmatched1s + counts[2] % 2 + 3) / 4;

也就是O(1)，意思是O(n)