思路

这个问题的核心是，我们需要遍历数组中所有出现过的数字，将它们逐一作为候选的目标数字 $x$，然后计算每种情况下所需的最小操作次数，最后在所有候选结果中取一个最小值。

那么，当我们选定了一个目标数字 $x$ 后，如何计算最少操作次数呢？

根据题意，操作是移除不包含 $x$ 的连续区间。这意味着所有不等于 $x$ 的元素都必须被移除。这些需要被移除的元素，被数组中原有的 $x$ 分隔成了若干个“连续块”。

例如，对于样例 [1, 2, 3, 1, 4, 5, 1]，如果我们选择 $x=1$，那么数组可以看作： [1, (2, 3), 1, (4, 5), 1]

这里，所有不为 1 的元素组成了两个连续的块：(2, 3) 和 (4, 5)。由于这两个块都不包含 1，我们可以分别对它们进行一次移除操作。因此，当 $x=1$ 时，需要 2 次操作。

我们可以推广这个结论：对于一个固定的目标数字 $x$，其操作次数就等于数组中由非 $x$ 元素组成的连续块的数量。

如何计算这些“块”的数量呢？我们可以通过 $x$ 在数组中出现的位置来确定。假设数字 $x$ 在数组中的所有位置（下标）为 $p_1, p_2, \dots, p_k$。

1. 在第一个 $x$（位置 $p_1$）之前，可能有一个非 $x$ 元素的块（从下标 $0$到 $p_1-1$）。如果 $p_1 > 0$，这里就算一次操作。
2. 在任意两个相邻的 $x$ 之间（位置 $p_i$ 和 $p_{i+1}$），如果它们不紧挨着（即 $p_{i+1} > p_i + 1$），那么它们之间就隔着一个非 $x$ 元素的块。每有这样一段间隔，操作次数就加一。
3. 在最后一个 $x$（位置 $p_k$）之后，可能有一个非 $x$ 元素的块（从下标 $p_k+1$ 到 $n-1$）。如果 $p_k < n-1$，这里也算一次操作。

综合起来，这就是计算固定 $x$ 的操作次数的方法。

为了解决整个问题，我们可以采用一个高效的算法，其时间复杂度为 $O(N)$：

1. 预处理：遍历一次数组，使用一个哈希表（或Map）来记录每个数字出现的所有下标。例如，positions[num] = [idx1, idx2, ...]。
2. 计算：遍历哈希表中的每一个唯一的数字 num 作为候选的 $x$。
3. 对于每个 num，根据它在 positions 中记录的下标列表，按照上述逻辑计算需要的操作次数 current_ops。
4. 在所有 current_ops 中找到最小值，即为最终答案。

这个算法的总时间复杂度是 $O(N)$，因为第一个步骤遍历数组是 $O(N)$，第二个步骤中，所有数字的下标列表长度之和也等于 $N$，所以总的计算时间也是 $O(N)$ 级别。对于 $N=100000$ 的数据规模是完全可以接受的。

C++

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

int main() {
    // 优化输入输出速度
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    // 使用map来存储每个数字出现的位置列表
    std::map<int, std::vector<int>> positions;
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        positions[a[i]].push_back(i);
    }

    // 初始化最小操作次数为一个较大的值
    int min_ops = n;

    // 遍历所有在数组中出现过的唯一数字
    for (auto const& [val, pos_vec] : positions) {
        int current_ops = 0;
        
        // 1. 检查第一个出现位置之前是否有元素
        if (pos_vec[0] > 0) {
            current_ops++;
        }

        // 2. 检查相邻两次出现之间是否有其他元素
        for (size_t i = 0; i < pos_vec.size() - 1; ++i) {
            if (pos_vec[i+1] > pos_vec[i] + 1) {
                current_ops++;
            }
        }

        // 3. 检查最后一次出现位置之后是否有元素
        if (pos_vec.back() < n - 1) {
            current_ops++;
        }
        
        // 更新全局最小值
        min_ops = std::min(min_ops, current_ops);
    }

    std::cout << min_ops << std::endl;

    return 0;
}

Java

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;

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

        // 使用HashMap来存储每个数字出现的位置列表
        Map<Integer, List<Integer>> positions = new HashMap<>();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
            // 如果map中没有这个键，则创建一个新的ArrayList
            positions.putIfAbsent(a[i], new ArrayList<>());
            // 将当前下标添加到对应数字的列表中
            positions.get(a[i]).add(i);
        }

        // 初始化最小操作次数为一个较大的值
        int minOps = n;

        // 遍历所有在数组中出现过的唯一数字 (map的键集合)
        for (int val : positions.keySet()) {
            List<Integer> posVec = positions.get(val);
            int currentOps = 0;

            // 1. 检查第一个出现位置之前是否有元素
            if (posVec.get(0) > 0) {
                currentOps++;
            }

            // 2. 检查相邻两次出现之间是否有其他元素
            for (int i = 0; i < posVec.size() - 1; i++) {
                if (posVec.get(i + 1) > posVec.get(i) + 1) {
                    currentOps++;
                }
            }

            // 3. 检查最后一次出现位置之后是否有元素
            if (posVec.get(posVec.size() - 1) < n - 1) {
                currentOps++;
            }
            
            // 更新全局最小值
            minOps = Math.min(minOps, currentOps);
        }

        System.out.println(minOps);
        scanner.close();
    }
}

Python

import sys
from collections import defaultdict

def solve():
    # 读取输入
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    # 使用defaultdict(list)来存储每个数字出现的位置列表
    positions = defaultdict(list)
    for i, num in enumerate(a):
        positions[num].append(i)

    # 初始化最小操作次数为一个较大的值
    min_ops = n

    # 遍历所有在数组中出现过的唯一数字
    for val in positions:
        pos_vec = positions[val]
        current_ops = 0

        # 1. 检查第一个出现位置之前是否有元素
        if pos_vec[0] > 0:
            current_ops += 1
        
        # 2. 检查相邻两次出现之间是否有其他元素
        for i in range(len(pos_vec) - 1):
            if pos_vec[i+1] > pos_vec[i] + 1:
                current_ops += 1
        
        # 3. 检查最后一次出现位置之后是否有元素
        if pos_vec[-1] < n - 1:
            current_ops += 1
            
        # 更新全局最小值
        min_ops = min(min_ops, current_ops)
        
    print(min_ops)

if __name__ == "__main__":
    solve()

题目内容

现在有一个长度为 $n$ 的数组。现在小明希望从数组中挑选一个数字 $x$ ，通过做一种清理操作，将原数组中的一些数字移除，使得最终数组中的数字都等于 $x$ 。这种移除操作一次可以删除数组中一段连续区间，但是这个区间中不能有任何数字等于 $x$ 。小明想知道对于一个数组，他最少需要多少次移除操作完成目标。

输入描述

第一行一个整数 $n(3<=n<=100000)$

第二行 $n$ 个整数，表示数组中的数字，数字范围在 $[1,100000]$ 。

输出描述

一个整数，表示最少所需的操作次数。

样例1

输入

7
1 2 3 1 4 5 1

输出

2

说明

其中一种方法为，挑选 $x=1$ ，一次删除 $2,3$ ，一次删除 $4,5$