题解 | #小红的顺子#

题目链接

小红的顺子

题目描述

小红有一个长度为 $n-1$ 的数组 $a$ ，其中的元素是 $1$ 到 $n$ 的排列中移除了一个数后得到的。

求这个数组能构成的顺子的最大长度。

顺子的定义为：一个序列中的数是连续递增的整数。例如，[1, 2, 3] 和 [8, 9] 都是顺子。

解题思路

这个问题的核心是找出给定数字集合中，最长的连续整数序列的长度。

例如，对于输入 1 2 4 5，我们拥有的数字集合是 {1, 2, 4, 5}。在这个集合中，最长的连续整数序列是 1, 2 和 4, 5，它们的长度都是2，所以最大长度是2。

原始数组中元素的顺序并不影响我们能构成的顺子，因此，最直接的解法是：

排序：首先对输入的数组 $a$ 进行升序排序。排序后，所有能构成顺子的数字都会被排列在一起。
线性扫描：遍历排序后的数组，用一个变量 current_length 来追踪当前顺子的长度，另一个变量 max_length 来记录历史上的最大顺子长度。
- 初始化 current_length = 1 和 max_length = 1（如果数组不为空，最小的顺子长度就是1）。
- 从数组的第二个元素开始遍历，比较当前元素 a[i] 和前一个元素 a[i-1]。
- 如果 a[i] == a[i-1] + 1，说明顺子仍在继续，我们将 current_length 加 1。
- 如果 a[i] != a[i-1] + 1，说明当前的顺子已经中断。此时，我们用 current_length 的值来更新 max_length，然后将 current_length 重置为 1，准备开始记录下一个可能的顺子。
结果：遍历结束后，需要再用 current_length 最后的值更新一次 max_length，以防止最长的顺子恰好在数组的末尾。最终的 max_length 就是答案。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    if (n <= 1) {
        cout << 0 << endl;
        return 0;
    }
    
    vector<int> a(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        cin >> a[i];
    }
    
    if (n - 1 == 0) {
        cout << 0 << endl;
        return 0;
    }

    sort(a.begin(), a.end());

    int max_length = 1;
    int current_length = 1;
    for (int i = 1; i < n - 1; ++i) {
        if (a[i] == a[i - 1] + 1) {
            current_length++;
        } else {
            max_length = max(max_length, current_length);
            current_length = 1;
        }
    }
    // 最后再更新一次，以处理最长顺子在末尾的情况
    max_length = max(max_length, current_length);

    cout << max_length << endl;

    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        if (n <= 1) {
            System.out.println(0);
            return;
        }

        int[] a = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            a[i] = sc.nextInt();
        }

        if (n - 1 == 0) {
            System.out.println(0);
            return;
        }

        Arrays.sort(a);

        int maxLength = 1;
        int currentLength = 1;
        for (int i = 1; i < a.length; i++) {
            if (a[i] == a[i - 1] + 1) {
                currentLength++;
            } else {
                maxLength = Math.max(maxLength, currentLength);
                currentLength = 1;
            }
        }
        maxLength = Math.max(maxLength, currentLength);

        System.out.println(maxLength);
    }
}

import sys

def solve():
    try:
        n_str = sys.stdin.readline()
        if not n_str: return
        n = int(n_str)
        
        if n <= 1:
            # 根据题意 n-1 个数，如果 n<=1 则没有数
            print(0)
            return

        line = sys.stdin.readline()
        if not line.strip():
            # 数组为空的情况
            print(0)
            return
            
        a = list(map(int, line.split()))

        a.sort()
        
        if not a:
            print(0)
            return

        max_length = 1
        current_length = 1
        for i in range(1, len(a)):
            if a[i] == a[i - 1] + 1:
                current_length += 1
            else:
                max_length = max(max_length, current_length)
                current_length = 1
        
        max_length = max(max_length, current_length)
        
        print(max_length)
    except (IOError, ValueError):
        return

solve()

算法及复杂度

算法：排序 + 线性扫描
时间复杂度: $\mathcal{O}(n \log n)$ ，瓶颈在于对数组进行排序。
空间复杂度: $\mathcal{O}(\log n)$ 或 $\mathcal{O}(n)$ ，取决于排序算法所使用的额外空间（例如，快速排序的递归栈深度或归并排序的辅助数组）。