统计数组中的不同切片
我试图解决this问题。统计数组中的不同切片
给出了一个整数M和一个非空的零索引数组A,其中包含N个非零的整数N 。在数组A的所有整数是小于 或等于M.
一对整数(P,Q)的,使得0≤P≤Q < N,被称为阵列A的切片 的切片由元素A [P],A [P + 1],..., A [Q]。不同的切片是仅由唯一数字组成的切片。 也就是说,切片中不会有多次出现单个号码。
例如,考虑整数M = 6和阵列A使得:
A[0] = 3 A[1] = 4 A[2] = 5 A[3] = 5 A[4] = 2
正好有九个不同的切片:(0,0),(0,1),(0,2), (1,0.1),(1,2),(2,2),(3,3),(3,4)和(4,4)。
目标是计算不同切片的数量。
在此先感谢。
#include <algorithm>
#include <cstring>
#include <cmath>
#define MAX 100002
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
using namespace std;
bool check[MAX];
int solution(int M, vector<int> &A) {
memset(check, false, sizeof(check));
int base = 0;
int fibot = 0;
int sum = 0;
while(fibot < A.size()){
if(check[A[fibot]]){
base = fibot;
}
check[A[fibot]] = true;
sum += fibot - base + 1;
fibot += 1;
}
return min(sum, 1000000000);
}
该解决方案是不正确的,因为你的算法是错误的。
首先,让我告诉你一个反例。让A = {2, 1, 2}
。第一次迭代:base = 0
,fibot = 0
,sum += 1.
没错。第二个:base = 0, fibot = 1
,sum += 2
。这也是正确的。最后一步:fibot = 2
,check[A[fibot]] is true
,因此base = 2
。但它应该是1
。所以你的代码返回1 + 2 + 1 = 4
而正确的答案1 + 2 + 2 = 5
。
正确的做法可能是这样的:从L = 0
开始。对于从0
到n - 1
的每个R
到n - 1
,请继续向右移动L
,直到子数组仅包含不同的值(您可以保留数组中每个值的出现次数,并使用A[R]
是可能出现的唯一元素比一次)。
您的代码还有一个问题:如果int
在测试平台上是32位类型(例如,如果A
的所有元素都不相同),那么sum
变量可能会溢出。
至于问题为什么你的算法不正确,我不知道为什么它应该是正确的。你能证明这个吗?对我来说,base = fibot
赋值看起来相当随意。
我明白了。非常感谢你。 –