主页 / coding / 问题 / 79596954
Accepted
CodeCrusader
Asked: 2025-04-29 00:52:43 +0800 CST

找到相邻 diff 小于 2 的子序列的最大长度

  • 772

问题陈述：

给定一个大小为 n 的整数数组 arr。

选择一个整数子序列并重新排列它们以形成一个循环序列，使得任意两个相邻整数（包括最后一个和第一个）之间的绝对差最多为 1。

找出可以选择的最大整数数。

笔记：

子序列是通过删除零个或多个元素而不改变剩余元素的顺序而形成的。

选定的整数可以按任意顺序重新排列。

该序列是循环的——最后一个整数和第一个整数被视为相邻的。

限制：

1 <= n <= 2 × 10^5

0 <= arr[i] <= 10^9

例子：

Input: arr = [4, 3, 5, 1, 2, 2, 1]
Output: 5
Explanation: maximum length subsequence is : [3, 1, 2, 2, 1], it can be rearranged to seq : [2, 1, 1, 2, 3] of length 5, note that the condition must be satisfied in circular also, means abs(seq[0] - seq[seq.length-1]) means abs(2-3) <= 0 

Input: arr = [3, 7, 5, 1, 5]
Output: 2
Explanation: maximum length subsequence is : [5,5] of length 2

Input: arr = [2, 2, 3, 2, 1, 2, 2]
Output: 7
Explanation: maximum length subsequence is : [2,2,3,2,1,2,2] of length 7

Input: arr = [1,2,3,4,5]
Output = 2
Explanation: maximum length subsequence is : [1,2] or [2,3] or [3,4] or [4,5], so length is 2.

请注意，子序列也应该满足循环条件这是我的代码：

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);
        }

        int max = 0;
        for (int num : freq.keySet()) {
            int count = freq.get(num);
            int countWithNext = freq.getOrDefault(num + 1, 0);
            int countWithPrev = freq.getOrDefault(num - 1, 0);
            max = Math.max(max, countWithPrev + count + countWithNext);
        }

        return max;
    }

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

我能够找到最大长度子序列，但无法找到如何满足循环条件，因此对于测试用例 [1,2,3,4,5]，我的代码返回 5 而不是 2。

此外，正如 John Bollinger 所评论的，该方法本身对于输入 [1,2,3,4,3,2] 失败

用较少的时间复杂度来解决这个问题的正确方法是什么？

java

2 个回答

  1. 用较少的时间复杂度来解决这个问题的正确方法是什么？

    请注意评论中@btilly 的提示：

    您的子序列有一个最小值，有一个最大值，并且它们之间的每个值都必须出现 2 次以上。

    这几乎是一个可以匹配的指纹，但在将其扩展为这样的指纹之前，让我们首先考虑一下为什么会这样。

    考虑一个连续循环序列中的成员s n，它既不是序列的最小值，也不是最大值。现在假设我们从s n开始遍历该循环。在返回s n之前，我们将遍历序列的最小值和最大值。由于序列是连续排列的，因此在这两个元素之间，我们必须遍历另一个与s n值相同的元素。因此，序列中每个既不是最小值也不是最大值的成员都必须出现至少两次。

    然而，最小值和最大值并非如此。其中一个或两个可能出现多次，但我们仍然可以形成一个只包含一个的循环。在最简单的情况下，单个数字出现一次就满足条件，但最小值和最大值可以各出现一次，并且元素总数可以是任意的，而不是恰好3。

    现在假设我们有一组连续的数字，顺序任意，每个数字至少出现两次，除了其中的最小值和最大值。我们可以先将它们按升序排列，然后从每个既不是最小值也不是最大值的数字中取出一个，并按降序将它们移到末尾，从而形成一个循环序列。例如，

    • 从2, 4, 3, 2, 3, 1, 3, 5, 5, 4开始，
    • 我们排序得到1, 2, 2, 3, 3, 3, 4, 4, 5, 5
    • 然后我们将一个 4、一个 3 和一个 2 移到最后，得到1, 2, 3, 3, 4, 5, 5, 4, 3, 2，满足要求

    因此，对于适合形成所需循环序列的数字集合，以下条件既是必要条件，也是充分条件：(i) 它们是连续的，并且 (ii) 每个既不是最小值也不是最大值的数字至少出现两次。

    现在你有了你的指纹。最坏情况下，可以在 O( nlogn )步内找到具有该指纹的最大序列，但具体细节留给你自己去解决。

    • 3
  2. Best Answer

    你的代码只根据直接“邻居”（按排序顺序）的频率来确定计数。当正确答案涉及超过3个不同的数字时，这将导致错误的结果。

    计算频率是一个好方法，但扫描范围不应仅限于当前值的直接相邻值。只有当您确定自己处于潜在范围的低端时，才查找相邻值也会很有帮助——这样您只需按升序扫描值即可。当一个值的频率为 1 或该值在负 1 的范围内不存在时，该值即为“低”。

    以下是循环（获得频率后）的工作方式：

            int max = 0;
        for (int num : freq.keySet()) {
            int count = freq.get(num);
            if (count != 1 && freq.containsKey(num-1)) continue;
            // We're at a low end of a range
            int groupCount = count;
            do {
                num++;
                count = freq.getOrDefault(num, 0);
                groupCount += count;
            } while (count > 1);
            max = Math.max(max, groupCount);
        }
        return max;

    假设哈希映射上的get和put操作的摊销时间复杂度为 O(1)，则该算法的时间复杂度为 O(𝑛)，其中 𝑛 是输入数组的大小。

    • 2

相关问题