c++中从排序数组中移除重复项

Question

我试图从排序数组中删除重复项。代码为一个测试用例提供正确的输出，但不能为多个测试用例提供正确的输出。我得到正确的输出与其他方法，但什么是错误的这种方法?我该如何解决这个问题?

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;

while(t--){

int n;
cin>>n;
int a[n],i,k,temp,count;

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

sort(a,a+n);

count=0;
for(i=0;i<n;i++){

if(a[i-1]-a[i]==0){

temp = a[i];
count++;
for(k=i;k<n;k++){
a[k] = a[k+1];  
}

}   
}

for(i=0;i<n-count;i++){
cout<<a[i]<<" ";
}
cout<<endl;


}

}

Answer 1

像这样的可变长度数组

int a[n],i,k,temp,count;

不是标准的c++特性。您应该使用标准容器std::vector<int>。

if语句

if(a[i-1]-a[i]==0){

当i=0时，由于表达式a[i-1]

，调用未定义行为。

同样的问题也存在于这个for循环

for(k=i;k<n;k++){
a[k] = a[k+1];  
}

当k=n - 1时，由于表达式a[k+1]。

而且，每次在找到重复元素后复制所有元素是低效的。

请注意，有一个标准算法std::unique可以用来代替你的循环。

如果要使用for循环，则可以实现如下内容

#include <iostream>
int main() 
{
int a[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
const size_t N = sizeof( a ) / sizeof( *a );

size_t n = 0;

for ( size_t i = 0; i < N; i++ )
{
if ( i == 0 || a[i] != a[n-1] )
{
if ( i != n  ) a[n] = a[i];
++n;
}
}

for ( size_t i = 0; i < n; i++ )
{
std::cout << a[i] << ' ';
}
std::cout << 'n';

return 0;
}

程序输出为

1 2 3 4 5 

如果使用标准算法std::unique，那么解决方案将更简单，因为不需要编写自己的for循环。

#include <iostream>
#include <iterator>
#include <algorithm>
int main() 
{
int a[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
auto last = std::unique( std::begin( a ), std::end( a ) );

for ( auto first = std::begin( a ); first != last; ++first )
{
std::cout << *first << ' ';
}
std::cout << 'n';

return 0;
}

程序输出与上面显示的相同，即

1 2 3 4 5 

Answer 2

我看到你的代码有两个主要问题，都是越界读取数组:

if(a[i-1]-a[i]==0)将在某一时刻被i==0调用，访问元素a[-1]。

:

for(k=i;k<n;k++){
a[k] = a[k+1];  
}

在最后一次循环迭代中，当k == n-1数组元素a[n]被访问时，这也是一次越界访问。