删除数组中k个连续元素后最大化剩余数组不同元素数的时间复杂度优化问询

First, let's break down why your current approach won't work for large arrays (up to 1,000,000 elements):

• Your code uses nested loops: for each of the O(n) possible window starting positions, you iterate through the entire array (O(n)) to build a HashSet. This results in O(n²) time complexity—way too slow for n=1e6, as it would require billions of operations.

The Optimized Approach (O(n) Time, O(m) Space) #

The key insight to reframe the problem:

The number of distinct elements remaining after deleting a k-length window = Total distinct elements in the array - Number of elements that exist only within that k-length window.

Our goal is to minimize the count of elements unique to the window (since subtracting a smaller number gives a larger result). Here's how to compute this efficiently:

1. Count Global Frequencies: First, calculate how many times each element appears across the entire array. This tells us if an element exists outside any given window.
2. Sliding Window for Loss Calculation: Use a sliding window to track how many elements in the current window have all their occurrences contained within the window—these are the elements we'll lose if we delete the window.
3. Compute Maximum Remaining Distinct: For each window, calculate the remaining distinct count as total_unique - current_loss, and keep track of the maximum value.

Step-by-Step Implementation #

Here's the optimized Java code, using arrays for frequency counting (faster than HashMaps for the given element value range):

int delete(int[] arr, int k) {
    int n = arr.length;
    if (k == n) {
        return 0; // Deleting the entire array leaves 0 distinct elements
    }
    
    // Step 1: Calculate global frequency of each element
    int maxElement = 1000000;
    int[] globalFreq = new int[maxElement + 1];
    for (int num : arr) {
        globalFreq[num]++;
    }
    
    // Step 2: Count total distinct elements in the array
    int totalUnique = 0;
    for (int freq : globalFreq) {
        if (freq > 0) {
            totalUnique++;
        }
    }
    
    // Step 3: Initialize sliding window for the first k elements
    int[] windowFreq = new int[maxElement + 1];
    int currentLoss = 0; // Number of elements only present in current window
    
    for (int i = 0; i < k; i++) {
        int num = arr[i];
        windowFreq[num]++;
        // If window now contains all occurrences of this element, increment loss
        if (windowFreq[num] == globalFreq[num]) {
            currentLoss++;
        }
    }
    
    int maxRemaining = totalUnique - currentLoss;
    
    // Step 4: Slide the window across the array
    for (int i = 1; i <= n - k; i++) {
        // Remove the element leaving the window (leftmost of previous window)
        int leftNum = arr[i - 1];
        windowFreq[leftNum]--;
        // If we previously had all occurrences in the window, now we don't
        if (windowFreq[leftNum] == globalFreq[leftNum] - 1) {
            currentLoss--;
        }
        
        // Add the new element entering the window (rightmost of current window)
        int rightNum = arr[i + k - 1];
        windowFreq[rightNum]++;
        // If we now have all occurrences in the window, increment loss
        if (windowFreq[rightNum] == globalFreq[rightNum]) {
            currentLoss++;
        }
        
        // Update the maximum remaining distinct count
        maxRemaining = Math.max(maxRemaining, totalUnique - currentLoss);
    }
    
    return maxRemaining;
}

Why This Works #

• Time Complexity: O(n) — we iterate through the array twice (once for global frequencies, once for sliding window), and each frequency operation is O(1).
• Space Complexity: O(m) where m is the maximum element value (1e6). For sparse element ranges, you could replace the arrays with HashMaps to save space, but arrays are faster for the given constraints.

Edge Cases Handled #

• When k equals the array length: returns 0 (deleting everything leaves nothing).
• When all elements are identical: deleting any k elements leaves 1 distinct element (if k < n).
• When the window contains no unique elements: remaining distinct count equals the total unique elements.

内容的提问来源于stack exchange，提问作者Learner