找到锤击后相同长度钉子的最大值

Question

我正在尝试解决这个问题：

给定一个正整数数组和一个整数Y，您最多可以用较小的值替换Y数组元素。您的目标是让数组以尽可能大的相同值的子集结束。返回这个最大子集的大小。

该数组最初排序递增的顺序，但你并不需要保存该属性。

因此，例如，如果数组是 [10,20,20,30,30,30,40,40,40] 并且Y  = 3，那么结果应该是 6，因为通过替换三个 40 可以得到六个 30与 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

C++ 实现如下所示，其中 A 是排序后的引脚尺寸数组，K 是可以锤击引脚的次数。
{1,1,3,3,4,4,4,5,5}，K=2 应该给出 5 作为答案
{1,1,3,3,4,4,4,5,5,6, 6,6,6,6,6}, K=2 应该给出 6 作为答案

int maxCount(vector<int>& A, int K) {
    int n = A.size();
    int best = 0;
    int count = 1;

    for (int i = 0; i < n-K-1; i++) {
        if (A[i] == A[i + 1])
            count = count + 1;
        else
            count = 1;
        if (count > best)
            best = count;
    }
    int result = max(best+K, min(K+1, n));
    
    return result;
} 

Answer 2

由于数组是从一开始就排序的，一个相当简单的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;
}