首页 > 试题广场 >

小红的区间删除

[编程题]小红的区间删除
  • 热度指数：533 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
小红拿到了一个数组，她准备进行最多一次以下操作：
选择两个相等的元素，将这两个元素之间的所有元素删除。
小红想知道，她最多可以删除多少个元素？

输入描述:
第一行输入一个正整数n，代表数组的大小。
第二行输入n个正整数a_i，代表数组的元素。
1\leq n \leq 200000
1\leq a_i \leq 10^9


输出描述:
一个整数，代表可以删除的最多数量。
示例1

输入

5
2 1 2 3 1

输出

2

说明

选择第二个数和第五个数（都是1），小红可以删除第三个数和第四个数。
算法知识视频讲解
添加回答
C++
牛客925889402号头像 牛客925889402号
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    for(int i = 0; i <= n; i++)
    {
        cin >> a[i];
    }

    unordered_map<int, int> first_occurrence;//存储每个元素第一次出现的索引

    int max_del = 0;//初始化被删除量

    for(int i = 0; i <= n; i++)
    {
        //检查当前元素是否已经出现过
        if(first_occurrence.count(a[i]))
        {
            //如果出现过，计算可以删除的元素数量
            int first_index = first_occurrence[a[i]];
            int del = i - first_index - 1;
            max_del = max(max_del, del);
        }
        else
        {
            //如果没有出现过，记录其第一次出现的索引
            first_occurrence[a[i]] = i;
        }
    }

    cout << max_del << endl;
    return 0;
}
发表于 2025-08-20 00:19:33 回复(0)
提交观点

问题信息

数组 字节跳动 哈希
来自：2024秋招-字节跳动...
难度：
1条回答 108浏览

热门推荐

相关试题

小红的区间删除

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号