求满足相邻差≤1的环形子序列最大长度的高效正确解法

问题描述 #

给定长度为n的整数数组arr，选择子序列并重排为环形序列，要求任意相邻元素（含首尾）的绝对差不超过1，求可选择的最大元素数量。

约束条件：

• 1 ≤ n ≤ 2×10^5
• 0 ≤ arr[i] ≤ 10^9

示例：

• 输入：[4, 3, 5, 1, 2, 2, 1]，输出：5
• 输入：[1,2,3,4,5]，输出：2

原代码错误分析 #

你编写的代码错误在于直接将三个连续数字的频率和作为候选值，但忽略了环形序列的首尾约束：当三个连续数字各出现一次时（如[1,2,3,4,5]中的任意三个连续数），无法排列成合法的环形序列（首尾元素差为2，不符合要求），但你的代码会将这种情况的和计入最大值，导致结果错误。

正确思路 #

合法的环形序列只能属于以下三种情况，我们需要分别计算每种情况的最大值：

1. 仅包含单个数字：最大长度为该数字的出现频率。
2. 包含两个连续数字：最大长度为两个数字的频率和（任意排列都满足相邻差≤1，环形首尾也符合要求）。
3. 包含三个连续数字x, x+1, x+2：只有当中间数字x+1的频率≥max(x的频率, x+2的频率)时，才能将x和x+2用x+1隔开，组成合法的环形序列，此时总长度为三者频率和；否则最多只能取其中两个连续数字的频率和。

实现代码 #

import java.util.*;

class Main {
    public static int solve(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        List<Integer> sortedNums = new ArrayList<>(freq.keySet());
        Collections.sort(sortedNums);
        int n = sortedNums.size();
        int maxLen = 0;

        // 情况1：单个数字的最大频率
        for (int count : freq.values()) {
            maxLen = Math.max(maxLen, count);
        }

        // 情况2：两个连续数字的频率和
        for (int i = 0; i < n - 1; i++) {
            int num1 = sortedNums.get(i);
            int num2 = sortedNums.get(i + 1);
            if (num2 == num1 + 1) {
                maxLen = Math.max(maxLen, freq.get(num1) + freq.get(num2));
            }
        }

        // 情况3：三个连续数字的合法组合
        for (int i = 0; i < n - 2; i++) {
            int num1 = sortedNums.get(i);
            int num2 = sortedNums.get(i + 1);
            int num3 = sortedNums.get(i + 2);
            if (num2 == num1 + 1 && num3 == num2 + 1) {
                int f1 = freq.get(num1);
                int f2 = freq.get(num2);
                int f3 = freq.get(num3);
                if (f2 >= Math.max(f1, f3)) {
                    maxLen = Math.max(maxLen, f1 + f2 + f3);
                } else {
                    maxLen = Math.max(maxLen, Math.max(f1 + f2, f2 + f3));
                }
            }
        }

        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(solve(new int[]{4,3,5,1,2,2,1})); // 预期输出：5
        System.out.println(solve(new int[]{1,2,3,4,5})); // 预期输出：2
        System.out.println(solve(new int[]{2,2,3,2,1,2,2})); // 预期输出：7
        System.out.println(solve(new int[]{3,7,5,1,5})); // 预期输出：2
        System.out.println(solve(new int[]{1,2,2,3})); // 预期输出：4
        System.out.println(solve(new int[]{1,1,2,3})); // 预期输出：3
    }
}

时间复杂度 #

• 统计频率：O(n)
• 排序不同数字：O(m log m)，其中m为数组中不同数字的数量（m ≤ n）
• 遍历计算三种情况：O(m)
  整体时间复杂度为O(n + m log m)，满足题目约束的性能要求。

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