Найти максимальное значение гвоздей той же длины после забивания

Question

Я пытаюсь решить эту проблему:

Учитывая массив положительных целых чисел и целое число Y , вам разрешено заменить не более Y элементы массива с меньшими значениями. Ваша цель состоит в том, чтобы массив получал как можно большее подмножество идентичных значений. Возвращает размер этого наибольшего подмножества.

Массив изначально сортируется в возрастающем порядке, но вы не должны сохранять это свойство.

Так, например, если массив [10,20,20,30,30,30,40,40,40] и Y = 3, результат должен быть 6, потому что вы можете получить шесть 30 с, заменив три 40 с 30-х годов. Если массив [20,20,20,40,50,50,50,50] и Y = 2, результат должен быть 5, потому что вы можете получить пять 20-х, заменив два из 50-х. с 20 с.

Ниже мое решение с O (nlogn) сложностью времени. (это правильно?) Интересно, смогу ли я дополнительно оптимизировать это решение?

Заранее спасибо.

public class Nails {

    public static int Solutions(int[] A, int Y) {
        int N = A.length;
        TreeMap < Integer, Integer > nailMap = new TreeMap < Integer, Integer > (Collections.reverseOrder());
        for (int i = 0; i < N; i++) {
            if (!nailMap.containsKey(A[i])) {
                nailMap.put(A[i], 1);
            } else {
                nailMap.put(A[i], nailMap.get(A[i]) + 1);
            }
        }
        List < Integer > nums = nailMap.values().stream().collect(Collectors.toList());

        if (nums.size() == 1) {
            return nums.get(0);
        }

        //else
        int max = nums.get(0);
        int longer = 0;
        for (int j = 0; j < nums.size(); j++) {
            int count = 0;
            if (Y < longer) {
                count = Y + nums.get(j);
            } else {
                count = longer + nums.get(j);
            }
            if (max < count) {
                max = count;
            }
            longer += nums.get(j);
        }
        return max;
    }


    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String[] input = scanner.nextLine().replaceAll("\\[|\\]", "").split(",");
            System.out.println(Arrays.toString(input));
            int[] A = new int[input.length - 1];
            int Y = Integer.parseInt(input[input.length - 1]);
            for (int i = 0; i < input.length; i++) {
                if (i < input.length - 1) {
                    A[i] = Integer.parseInt(input[i]);
                } else {
                    break;
                }
            }
            int result = Solutions(A, Y);
            System.out.println(result);
        }
    }
}

Answer 1

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

public static int doIt(final int[] array, final int y) {
    int best = 0;
    int start = 0;
    while (start < array.length) {
        int end = start;
        while (end < array.length && array[end] == array[start]) {
            ++end;
        }

        // array[start .. (end-1)] is now the subarray consisting of a
        // single value repeated (end-start) times.
        best = Math.max(best, end - start + Math.min(y, array.length - end));

        start = end; // skip to the next distinct value
    }
    assert best >= Math.min(y + 1, array.length); // sanity-check
    return best;
}

Answer 2

Сначала, переберите все гвозди и создайте ха sh H, в котором хранится количество гвоздей для каждого размера. Для [1,2,2,3,3,3,4,4,4] H должно быть:

size     count
 1    :    1
 2    :    2
 3    :    3
 4    :    3

Теперь создайте небольшой алгоритм для оценки максимальной суммы для каждого размера S, учитывая Y:

BestForSize(S, Y){
    total = H[S]
    while(Y > 0){
        S++
        if(Y >= H[S] and S < biggestNailSize){
            total += H[S]
            Y -= H[S]
        }
        else{
            total += Y
            Y = 0
        }
    }
    return total;
}

Ваш ответ должен быть max(BestForSize(0, Y), BestForSize(1, Y), ..., BestForSize(maxSizeOfNail, Y)).

Сложность O (n²). Совет по оптимизации - начать с конца. Например, после того, как у вас есть максимальное значение гвоздей в размере 4, как вы можете использовать свой ответ, чтобы найти максимальное количество в размере 3?