时间戳

首页 > 解决方案 > 最长的不同数字的子数组可能吗？

c++ - 最长的不同数字的子数组可能吗？

问题描述

这是今天比赛中的一个问题，（已经结束，我的解决方案只有 25% 的例子是正确的）

问题：一个旅行者旅行了 N 天，每天访问一个城市。一些城市已多次访问。编写一个程序，告诉我们旅行者每天去不同城市的最长时间的长度！

输入：天数（1 < N < 100,000），在下一行中，城市的“名称” 1 < S[i] < N（它们只是单独的整数）。

示例输入：

8

1 2 1 6 3 5 2 5

输出：5 ----- 解释：(1 6 3 5 2) （但我认为按照这个逻辑 2 1 6 3 5 也是正确的？）

这是我的解决方案，它对 25% 的测试用例给出了正确答案，而对另外 75% 的测试用例给出了错误答案。我们只能看到两个测试用例，另一个是 10000 个数字，我不会在这里复制。

#include <iostream>
#include <vector>
#include <set>
#include <bits/stdc++.h>
using namespace std;



    int main()
    {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        int n, input;
        cin >> n;
        vector<int> cities;
        for(int i = 0; i < n; i++)
        {
            cin >> input;
            cities.push_back(input);
        }
        int maxlength = 0;
        set<int> myset;
        for(int i = 0; i < n; i++)
        {
            if(myset.find(cities[i]) != myset.end())
            {
                myset.clear();
            }
            myset.insert(cities[i]);
            if(myset.size() > maxlength)
                maxlength = myset.size();
        }
        cout << maxlength << endl;
        return 0;
    }

我相信这个问题实际上归结为在给定数组中找到最长的一组不同数字（我可能错了）。但是，据该网站称，我的解决方案并不完全正确。

PS：我觉得奇怪的是它有时给出正确的答案，有时给出不正确的答案。它永远不会超出时间障碍。我认为一个程序要么总是正确要么总是不正确，无论如何，对不起，如果这个问题已经在这里被问过，我没有找到这样一个完全相同的问题。显然，我对各种批评持开放态度，毕竟，我们是来学习的。

标签： c++c++14

解决方案

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <complex>
#include <numeric>

using namespace std;

int main()
{
    vector<int> cities = {1, 2, 1, 6, 3, 5, 2, 5};
        
    vector<int>::size_type startingCityIndex = 0;
    vector<int>::size_type maxStartCityIndex;
    vector<int>::size_type maxEndCityIndex;
    unsigned maxDistance = 0;
    unordered_set<int> visitedCities = {cities[0]};
    
    // Create distance vector F[n] := f[n+1] - f[n] (undefined for n = cities.size() - 1)
    vector<int> distances;
    for(vector<int>::size_type cityIndex = 0; cityIndex < cities.size() - 1; ++cityIndex)
        distances.push_back(abs(cities[cityIndex + 1] - cities[cityIndex]));
    
    // Suppose he travels to each city from startingCityIndex
    for(vector<int>::size_type traveledCityIndex = 1; traveledCityIndex < cities.size(); ++traveledCityIndex)
        // If he has not visisted the city
        if(visitedCities.find(cities[traveledCityIndex]) == visitedCities.end()) {
            // If the visisted city isn't the last one
            if(traveledCityIndex != cities.size() - 1)
                visitedCities.insert(cities[traveledCityIndex]);
            // Else it is the last one
            else {
                unsigned distance = accumulate(distances.cbegin() + startingCityIndex, distances.cend(), 0U);
                if(distance > maxDistance) {
                    maxEndCityIndex = traveledCityIndex;
                    maxStartCityIndex = startingCityIndex;
                }
            }
        // Else he has visited the city. Consider his path up to that point and start new path, clearing visitedCities and setting new startingCityIndex
        } else {
            unsigned distance = accumulate(distances.cbegin() + startingCityIndex, distances.cbegin() + traveledCityIndex - 2, 0U);
            if (distance > maxDistance) {
                maxDistance = distance;
                maxStartCityIndex = startingCityIndex;
                maxEndCityIndex = traveledCityIndex - 1;
            }
            while(cities[startingCityIndex] != cities[traveledCityIndex])
                visitedCities.erase(cities[startingCityIndex++]);
            visitedCities.erase(cities[startingCityIndex++]);
            --traveledCityIndex;
        }
    
    // Output answer
    for(vector<int>::size_type cityIndex = maxStartCityIndex; cityIndex < maxEndCityIndex; ++cityIndex)
        cout << cities[cityIndex] << " ";
    cout << cities[maxEndCityIndex] << endl;

    // Success!
    return EXIT_SUCCESS;
}

O(n) 内存，因为unordered_set可能存储所有城市（如果路径是整个输入序列）。

startingCityIndex并且traveledCityIndex最多在城市上前进一次，从不回溯，所以没有set::findor的循环unordered_set::find将是 O(n)。

find我们必须考虑到可能调用多达 n 个方法的事实。set::find最坏情况为 O(logn)，使得整体算法为 O(nlogn)。但是，unordered_set::find具有平均情况 O(1) 和最坏情况 O(n)，使得平均性能 O(n) 和最坏情况 O(n^2)。当应用于整数时，散列应该是相当一致的，所以我会选择unordered_set，预测它会更接近 O(1) 而不是 O(n) find。

推荐阅读