Ошибка вложенного цикла - Java

Question

Я пытаюсь решить эту проблему с Leetcode, но она не прошла 3 теста.Я не могу понять, что я делаю неправильно.Вот мой код:

public int findContentChildren(int[] greed, int[] size) {

    if (size.length == 0 || greed.length == 0) return 0;

    int satisfied = 0;

    for (int i = 0; i < greed.length; i++) {
        for (int j = 0; j < size.length; j++) {
            if (greed[i] <= size[j]) {
                satisfied++;
                size[j] = -1;
                break;
            }
        }
    }
    return satisfied;
}

"Предположим, что вы замечательный родитель и хотите дать своим детям немного печенья. Но вы должны дать каждому ребенку не более одного печенья. У каждого ребенка у меня есть фактор жадности gi, который является минимальным размером файла cookie, которым будет удовлетворен дочерний элемент, и каждый файл cookie j имеет размер sj. Если sj> = gi, мы можем назначить файл cookie для дочернего элемента i, а дочерний элемент i будет содержимымВаша цель - максимизировать количество дочерних элементов содержимого и вывести максимальное число. Примечание. Можно предположить, что коэффициент жадности всегда положительный. Невозможно назначить более одного файла cookie одному дочернему элементу.

Пример 1:

Ввод: [1,2,3], [1,1]

Ввод: 1

Объяснение: У вас 3 детей и 2 печенья.3 детей - это 1, 2, 3.

И хотя у вас есть 2 куки-файла, так как их размер равен 1, вы можете сделать так, чтобы у ребенка был только коэффициент жадности 1. Вам нужно вывести 1 ".

https://leetcode.com/problems/assign-cookies/

Answer 1

Как указывают другие ответы.Вам нужно отсортировать оба массива перед запуском цикла for.Для большей ясности я внес изменения именно в то место, где они должны быть.

import java.util.*;
class Solution {
    public int findContentChildren(int[] greed, int[] size) {
        int satisfied = 0;
    Arrays.sort(greed);
    Arrays.sort(size);
    for (int i = 0; i < greed.length; i++) {
        for (int j = 0; j < size.length; j++) {
            if (greed[i] <= size[j]) {
                satisfied++;
                size[j] = 0;
                //greed[i]=0;
                break;
            }
        }
    }
    return satisfied;
    }
}

изменения:

import java.util.*;

, а затем отсортировали оба массива перед использованием цикла for,

Arrays.sort(greed);
Arrays.sort(size);

Также, поскольку удовлетворенное значение инициализируется в 0, нам не нужно выполнять возврат граничного условия.Следовательно, приведенная ниже проверка удалена

if (size.length == 0 || greed.length == 0) return 0;

Answer 2

Сортировка двух массивов.

Arrays.sort(greed);
Arrays.sort(size);

Предположим, жадность равна [4,5], а размер - [5,4] в приведенном выше примере.Без сортировки (согласно вашей логике) может быть удовлетворен только один ребенок, но с помощью сортировки вы можете удовлетворить обоих детей.

Answer 3

Пара вещей, которые я нашел отсутствующими в вашем коде.

Вы пробуете все куки для ребенка.Это делается до тех пор, пока одно печенье не удовлетворит ребенка.Несмотря на то, что cookie помечен как -1, время амортизации велико, поскольку проверки на -1 все еще будут выполняться снова.В идеале, эту проверку следует избегать, поскольку cookie уже используется.

Во-вторых, вы можете не соответствовать perfect cookie, если массивы не отсортированы.Причина присутствует в других ответах здесь.

Пометка использованного файла cookie как -1 была разумным шагом, но для этого вопроса не требуется.Время выполнения равно O (nm), но его можно выполнить за O (n), выполнив итерацию отсортированных массивов вместе и поддерживая указатели на чтение дочернего и последнего использованного cookie.

Сложность по времени вычисляется без учета части сортировки.

Answer 4

Вы просматриваете файлы cookie и детей в порядке их появления, а не в отсортированном порядке.Если у вас есть cookie-файлы 1, 2, 3 и дочерние файлы 3, 2, 1, вы совпадете только с двумя cookie-файлами, когда у вас есть идеальное совпадение.Вам нужно отсортировать массивы или использовать структуру данных, например, кучу, чтобы максимизировать распространение файлов cookie.