Как я могу изменить этот код, чтобы иметь временную сложность o (log n) или o (n) вместо o (n^2)

Question

Как я могу решить это в o (n) или o (logn)?

После уроков русские группы школьников вышли на улицу и решили посетить Поликарпус, чтобы отпраздновать свой день рождения. Мы знаем, что i-я группа состоит из друзей si (1 ≤ si ≤ 4), и они хотят пойти в Поликарпус вместе. Они решили добраться туда на такси. Каждый автомобиль может перевозить не более четырех пассажиров. Какое минимальное количество автомобилей понадобится детям, если все члены каждой группы будут ездить на одном такси (но одно такси может принимать более одной группы)? Ниже мой подход, но в о (п^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), так как вы должны изучить каждую группу.

Вы можете сделать это одним обходом набора групп и кеша: так что O (N).

Для каждой группы подсчитайте размер.

1. Если это 4, добавьте такси.
2. Если это 3, попытайтесь выполнить сопряжение с кешем 1, если нет, кешем этой группы.
3. Если это 1, попытайтесь установить пару с кешем 3, если нет, кешем этой группы.
4. Если это 2, попробуйте выполнить пару с кешированным 2, если нет, кешем этой группы.

Осмотрите свой кэш. Пара любой группы 2 с одной или более группой 1. Затем пара всех оставшихся групп 1.

Answer 2

Аналогичным решением к тому, что предложил Вирсавия, но на основе числа групп каждого размера вместо кэширования:

Идите по списку группы один раз и подсчитайте количество их каждого размера. Это требуется 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 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) в целом.