Problem
How do you remove repeated values from a Int Array returning the resultant array in the same order as the original?
Solution
In-place removing duplicates
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : remove repeated values from a Int Array returning the resultant
array in the same order as the original.
Created Date : 21-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
using namespace std;
void RemoveRepeatedValue(int* arr, int& len)
{
if(len < 2) return;
int uniqueLen(1);
int head(1);
while(head < len){
bool found = false;
for(int i = 0; i < uniqueLen; ++i){
if(arr[i] == arr[head]){
found = true;
break;
}
}
if(!found){
arr[uniqueLen ++] = arr[head];
}
head ++;
}
len = uniqueLen;
}
int main(int argc, char* argv[])
{
// Single input
cout << "Single input" << endl;
int testCase[20] = {1};
int len = 1;
cout << "Before removing duplicates" << endl;
for(int j = 0; j < len; j++){
cout << setw(3) << testCase[j];
}
cout << endl;
RemoveRepeatedValue(testCase, len);
cout << "After removing duplicates" << endl;
for(int j = 0; j < len; j++){
cout << setw(3) << testCase[j];
}
cout << endl;
cout << "-------------------------" << endl;
// All duplicated
cout << "All duplicated" << endl;
testCase[0] = 10;
testCase[1] = 10;
testCase[2] = 10;
testCase[3] = 10;
testCase[4] = 10;
len = 5;
cout << "Before removing duplicates" << endl;
for(int j = 0; j < len; j++){
cout << setw(3) << testCase[j];
}
cout << endl;
RemoveRepeatedValue(testCase, len);
cout << "After removing duplicates" << endl;
for(int j = 0; j < len; j++){
cout << setw(3) << testCase[j];
}
cout << endl;
cout << "-------------------------" << endl;
// Random input
cout << "Random input" << endl;
for(int i = 1; i < 20; ++i){
int len = i;
int* arr = new int[len];
cout << "Before removing duplicates" << endl;
for(int j = 0; j < len; j++){
arr[j] = rand() % 20;
cout << setw(3) << arr[j];
}
cout << endl;
RemoveRepeatedValue(arr, len);
cout << "After removing duplicates" << endl;
for(int j = 0; j < len; j++){
cout << setw(3) << arr[j];
}
cout << endl;
cout << "-------------------------" << endl;
delete[] arr;
}
return 0;
}
Output
Single input
Before removing duplicates
1
After removing duplicates
1
-------------------------
All duplicated
Before removing duplicates
10 10 10 10 10
After removing duplicates
10
-------------------------
Random input
Before removing duplicates
1
After removing duplicates
1
-------------------------
Before removing duplicates
7 14
After removing duplicates
7 14
-------------------------
Before removing duplicates
0 9 4
After removing duplicates
0 9 4
-------------------------
Before removing duplicates
18 18 2 4
After removing duplicates
18 2 4
-------------------------
Before removing duplicates
5 5 1 7 1
After removing duplicates
5 1 7
-------------------------
Before removing duplicates
11 15 2 7 16 11
After removing duplicates
11 15 2 7 16
-------------------------
Before removing duplicates
4 2 13 12 2 1 16
After removing duplicates
4 2 13 12 1 16
-------------------------
Before removing duplicates
18 15 7 6 11 18 9 12
After removing duplicates
18 15 7 6 11 9 12
-------------------------
Before removing duplicates
7 19 15 14 3 11 2 13 13
After removing duplicates
7 19 15 14 3 11 2 13
-------------------------
Before removing duplicates
4 1 11 13 8 7 4 2 17 17
After removing duplicates
4 1 11 13 8 7 2 17
-------------------------
Before removing duplicates
19 3 1 9 18 16 15 10 2 8 6
After removing duplicates
19 3 1 9 18 16 15 10 2 8 6
-------------------------
Before removing duplicates
0 2 4 8 6 5 10 9 10 10 6 1
After removing duplicates
0 2 4 8 6 5 10 9 1
-------------------------
Before removing duplicates
13 8 9 3 4 14 16 0 6 16 11 8 4
After removing duplicates
13 8 9 3 4 14 16 0 6 11
-------------------------
Before removing duplicates
19 6 3 17 18 18 2 9 1 13 15 19 18 4
After removing duplicates
19 6 3 17 18 2 9 1 13 15 4
-------------------------
Before removing duplicates
10 17 6 13 6 1 5 4 12 10 9 17 13 17 12
After removing duplicates
10 17 6 13 1 5 4 12 9
-------------------------
Before removing duplicates
6 10 1 16 15 7 15 14 11 12 10 10 1 4 6 10
After removing duplicates
6 10 1 16 15 7 14 11 12 4
-------------------------
Before removing duplicates
7 11 7 17 17 7 13 3 5 9 9 18 1 8 2 6 6
After removing duplicates
7 11 17 13 3 5 9 18 1 8 2 6
-------------------------
Before removing duplicates
10 13 8 0 11 2 15 10 19 4 17 8 3 15 1 2 10 11
After removing duplicates
10 13 8 0 11 2 15 19 4 17 3 1
-------------------------
Before removing duplicates
16 14 0 16 1 8 19 8 4 1 14 13 19 18 18 0 8 7 7
After removing duplicates
16 14 0 1 8 19 4 13 18 7
-------------------------
Press any key to continue . . .