How to remove repeated values in array?

[davi]

case 1: input 1 --> ouput 2;
case 2: input 1234 --> output 1234;
case 3: input 1223 --> output 123;
case 4: input 1233 --> output 123;
case 5: input 1222 --> output 12;
case 6: input 1122 --> output 12;
case 7: input 1111 --> output 1;

I've try to do this question with the following code.
but i fail to pass the case 5 and 7. please help.

#include <iostream>
using namespace std;
//assume increasing order
int main()
{
	int n;
	int arr[10];// assume no more than 10, otherwise use dynamic
	do
	{
		cout << "Input n(<=10): ";
		cin>> n;
	}while(n>10);

	for(int i=0; i<n; i++)
	{
		cout<<"Input arr[" << i << "]: ";
		cin>>arr[i];
	}
	

	for(int i=0; i<n-1; i++)
	{
		if(arr[i]==arr[i+1])
		{
			for(int j=i; j<n-1; j++)
			{
				arr[j]=arr[j+1];
			}
			n--;
		}
	}

	for(int i=0; i<n; i++)
	{
		cout<<arr[i]<<endl;
	}

	return 0;
}

[zijuan0810]

#include <iostream>
using namespace std;
//assume increasing order
int main()
{
	int n;
	int arr[10];// assume no more than 10, otherwise use dynamic
	do
	{
		cout << "Input n(<=10): ";
		cin>> n;
	}while(n>10);

	for(int i=0; i<n; i++)
	{
		cout<<"Input arr[" << i << "]: ";
		cin>>arr[i];
	}
	
	int repeats = 0;  //add
	for(i=0; i<n-1; i++)
	{
		if(arr[i]==arr[i+1])
		{
			for(int j=i; j<n-1; j++)
			{
				arr[j]=arr[j+1];
			}
			//n--;
			repeats++;
		}

	}
	n -= repeats;   //add

	for(i=0; i<n; i++)
	{
		cout<<arr[i]<< "  ";
	}

	return 0;
}

but this codes still have some bugs, such as:
case 1: input 12233 --> output 12;
I am working with it.

[zwA4jE8b]

basically you just need an algorithm that takes a position and compares it to the previous position. If they are different, store the new one, if they are the same, discard the new one.


1223

1) 12 - Good
2) 22 - Discard second two
3) 23 - Good

I had to do something similar to this when writing a SoundEx function.

[zijuan0810]

#include <iostream>
using namespace std;
//assume increasing order
int main()
{
	int n;
	int arr[10];// assume no more than 10, otherwise use dynamic
	int new_arr[10] = {0};	//store repeated elements
	do
	{
		cout << "Input n(<=10): ";
		cin>> n;
	}while(n>10);

	cout << "Input arr[0]: ";
	cin >> arr[0];
	new_arr[0] = arr[0];

	int j = 1;
	for( int i = 1; i < n; i++)
	{
		cout << "Input arr[" << i << "]: ";
		cin >> arr[i];	
		if(arr[i] != arr[i-1])
			new_arr[j++] = arr[i];

	}

	//output the result
	for(i = 0; i < j; i++)
		cout << new_arr[i] << "  ";
	cout << endl;

	return 0;
}

[davi]

Thanks for your useful reply and the program really works well.

However, my teacher give me constraints to do it.

1. Only one array can be used.
2. The values inside the array is preset, not actually input by the user.
(such as: int arr[10]={1,2,2,3,4,4,5,5,5,5})

So i still thinking the other algorithm to fulfill the requirement.

Thanks again.

[zwA4jE8b]

what you need to do when you find a repeated number is move all the positions above it down one. That will eliminate the duplicate as well as move things into correct position.


so your first iteration will compare 1 and 2. thats ok
i++;
compare 2 and 2. Remove second 2 by moving 2,4,4,5,5,5,5 all down one and setting last pos to 0
updated array looks like {1,2,3,4,4,5,5,5,5,0}
i++;
compare 2 and 3, thats ok.
i++;
compare 3 and 4, thats ok.
i++;
compare 4 and 4. Remove second 4 by moving 5,5,5,5 down one and setting last pos to 0
updated array looks like {1,2,3,4,5,5,5,5,0,0}
i++;
repeat above steps.

[zijuan0810]

I spent too much time solving this problem, but I failed. Luckily, I look out a good algorithm with the following code.

#include <iostream>
using namespace std;

//no need to assume increasing order
int main()
{
	// no need to assume no more than 10, any number can be work
	int array_size;//the length of preset array
	do
	{
		cout << "Input array_size(<=10): ";
		cin >> array_size;
	}while(array_size > 10);


	int *arr = new int[array_size];
	int i, j;

  
	for(i = 0; i < array_size; i++)
	{
		cout<<"Input arr[" << i << "]: ";
		cin>>arr[i];
	}

	cout << "the original array output: " << endl;
	for(i = 0; i < array_size; i++)
		cout << arr[i] << "  ";
	
	cout << endl;
	cout << "the single element output: " << endl;
    cout << arr[0] << "  ";	//first element

    for(i = 1; i < array_size; i++) //the critical codes
	{
		for(j = 0; j < i; j++) 
		{
			if(arr[j] == arr[i])
				break;
			if(j == i-1)
				cout << arr[i] << "  ";
		}    
	} 
	
	delete [] arr;
	cout << endl;

	return 0;
}

such as: int arr[10]={1,2,2,3,4,4,5,5,5,5} can be work well.
such as: int arr[10]={5,2,1,3,4,4,5,4,5,5} can be work well too.

[zwA4jE8b]

int new_sz = arraysize;
for (int i = 0; i < arraysize - 1; i++)
{
      if (arr[i] == arr[i + 1])
      {
           for (int j = arr[i + 1]; j < arraysize; j++)
                 arr[j] = arr[j+1];
           arr[arrsize - 1] = 0;
           new_sz--;
       }
}

to output just use a for loop from '0' to '< new_sz'

where arr[] is your array. and arraysize is the declaring subscript. new_size holds the new size.

[davi]

Thanks for both of your great help!
zijuan you teach me an i/o manipulation and new array way.
MFS you teach me an array manipulation way.

zijuan's solution is so complete.
So i am going to post the array manipulation way to let us have 2 algorithm to use.

#include <iostream>
using namespace std;
//assume increasing order

int main()
{
	int n;
	int arr[10];// assume no more than 10, otherwise use dynamic
	do
	{
		cout << "Input n(<=10): ";
		cin>> n;
	}while(n>10);

	for(int i=0; i<n; i++)
	{
		cout<<"Input arr[" << i << "]: ";
		cin>>arr[i];
	}
	
	int m=n;
	/* //below is the other way round
	for(int i=0; i<n-1 && i<m; i++)
	{
		while(arr[i]==arr[i+1])
		{
			for(int j=i; j<n-1; j++)
			{
				arr[j]=arr[j+1];
				if(j+1==n-1)
				{
					arr[j+1]=NULL;
				}
			}
			m--;	
		}
	}
	*/
	for(int i=1; i<n && i<=m; i++) 
	{
		while(arr[i-1]==arr[i])
		{
			for(int j=i; j<n; j++)
			{
				arr[j-1]=arr[j];
				if(j==n-1)
				{
					arr[j]=NULL;
				}
			}
			m--;
		}
	}

	for(int i=0; i<m; i++)
	{
		cout<<arr[i]<<endl;
	}

	return 0;
}

//test cases
/*
1		1
1111	1
1234	1234
1233	123
1223	123
1122	12
1222	12
1112	12


1223445555 12345

5213445455 52134(optional)

*/

Really, THANKS AGAIN FOR YOUR GREAT HELP! ^O^