Array problem

Hello! I am trying to find a way to do something like this:
input: 3 4 7 4 3 3 7
output: 3 4 7

So what I am trying to do is from an array of integers to take numbers that occur only once. If 3 is in that away I am trying to input it in a different array only once.

input: 8 3 2 9 8 9 2
output: 2 3 8 9

I cannot find a way to solve this, and I have been trying to solve it for a long time.
closed account (3TXyhbRD)
It looks like you want your output to be sorted. If this is the case, there are enough sorting algorithms online to help you out. I would personally go for bubble/insertion sort and specialize it a bit. When you want to insert a new element you will need to go through, at most, all elements to find the right spot. If that element already exists don't insert it (one extra if in the standard algorithm).

Example (for input: 8 3 2 9 8 9 2):

Result array = [ ]
Read number (8)
Result array = [ ]
                ^ (beginning of array => insert)
Result array = [ 8 ]

Read number (3)
Result array = [ 8 ]
                 ^ (is 3 greater than 8? No => move to a lower position)
Result array = [ 8 ]
                ^ (beginning of array => insert)
Result array = [ 3, 8 ]

... (inserting 2 and 9 using the same fashion)

Result array = [ 2, 3, 8, 9 ]

Read number (8)
Result array = [ 2, 3, 8, 9 ]
                          ^ (is 8 greater than 9? No => move to a lower position)
Result array = [2, 3, 8, 9 ]
                      ^ (is 8 equal to 8? Yes => don't insert)
Result array = [ 2, 3, 8, 9 ]

... (same fashion for the rest)


This should help you with your homework ;)
I will try it out and see what I can do, thanks!
Last edited on
This sounds like you need to use a sorted set.
http://www.cplusplus.com/reference/set/set/
Last edited on
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
  long Arr[] = {3,4,7,4,3,3,6,4,6,8,9,4,3,2,5,1,5,9};
  int size = (int)(sizeof Arr / sizeof Arr[0]);
  long temp[size];
  sort(Arr, Arr + size);
  
//   for (int h = 0; h < size; ++h)
//     cout << Arr[h] << " " << h <<endl;
  
  for (int y = 0, c = 0; y < size; ++y)
  {
    if (Arr[y] != Arr[y+1])
    {
      temp[c] = Arr[y];
      cout << temp[c] << " ";
      ++c;
    }
  }
  
  cout << endl;
  
  return 0;
}


$ ./File
1 2 3 4 5 6 7 8 9
Last edited on
Personally I would've stored the numbers in a map<unsigned, unsigned>. The map is sorted naturally and you have bonus of being able to store how many of each you find.

e.g
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
map<unsigned, unsigned> data;

unsigned input = 0;
// read input 
data[input]++;

// read input
data[input]++;

// in C++11 you could do:
cout << "Output: "
for (auto i = data.begin(); i != data.end(); ++i) 
  cout << i->first << " ";
cout << endl;

// In C++01 you could do:
map<unsigned, unsigned>::iterator i;
cout << "Output: "
for (i = data.begin(); i != data.end(); ++i) 
  cout << i->first << " ";
cout << endl;
I think that you have not to change the original array. In this case the approach is simple. Before adding a new element from the source array to the destination array you should check that there is no such element in the destination array.:)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/* code by usandfriends */
#include <iostream>

main()
{
	int howmany,i,n,j,counter,lowest,highest,tmp;
	
	lowest=0;
	highest=0;
	
	std::cout<<"How long is your list?  ";
	std::cin>>howmany;
	std::cout<<std::endl<<std::endl;
	
	int tally[howmany];
	
	for(i=0;i<howmany;i++)
	{
		std::cout<<"Item number "<<i+1<<":  ";
		std::cin>>tally[i];
		if(lowest>=tally[i])
		{
			lowest=tally[i];
		}
		if(highest<=tally[i])
		{
			highest=tally[i];
		}
	}
	
	std::cout<<std::endl<<std::endl<<"We will now find out how many different values are in your list."<<std::endl<<std::endl;
	
	  for(counter=0;counter<=howmany;counter++) //bubble sort
      {
            for(j=1;j<howmany;j++)
            {
                  if(tally[j]>tally[j-1])
                        {;}
                        
                  else
                  {
                        tmp=tally[j];
                        tally[j]=tally[j-1];
                        tally[j-1]=tmp;
                  }
            }
      }
	
	for(i=0;i<howmany;i++) //count repeating array items
	{
		if(i!=0)
		{
			if(tally[i]!=tally[i-1])
			{
			}
			if(tally[i]!=tally[i+1])
			{
				std::cout<<" "<<tally[i]<<" ";
			}
		}
	}
}
Last edited on
If to use sorting then the algorithm is following.
1). You copy the original array in the destination array.
2). Sort the destination array.
3) Apply standard algorithm std::unique.

For example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <algorithm>
#include <iterator>

int main()
{
	int a[] = { 1, 7, 3, 3, 1, 6, 5, 7, 4, 6 };
	int b[sizeof( a ) / sizeof( *a )];

	std::copy( std::begin( a ), std::end( a ), std::ostream_iterator<int>( std::cout, " " ) );
	std::cout << std::endl;

	std::copy( std::begin( a ), std::end( a ), std::begin( b ) );

	std::sort( std::begin( b ), std::end( b ) );

	auto last = std::unique( std::begin( b ), std::end( b ) );

	std::copy( std::begin( b ), last, std::ostream_iterator<int>( std::cout, " " ) );
	std::cout << std::endl;

	std::cout << "The new array contains " 
		      << std::distance( std::begin( b ), last ) 
		  << " unique elements." << std::endl;
}



The output is

1 7 3 3 1 6 5 7 4 6
1 3 4 5 6 7
The new array contains 6 unique elements.



But as I said early all these approaches based on sorting have one serious shortage of breaking the original order of elements in the array.

So I would prefer the approach I described early in my previous post.


EDIT: In the presented code the two statements

1
2
3
	std::copy( std::begin( a ), std::end( a ), std::begin( b ) );

	std::sort( std::begin( b ), std::end( b ) );


could be substituted for one statement

std::partial_sort_copy( std::begin( a ), std::end( a ), std::begin( b ), std::end( b ) );
Last edited on
Topic archived. No new replies allowed.