One of the final exam problems is going to be a problem involving the use of arrays and loops. To help you prepare for this exam problem, I am going to be solving a problem involving arrays that is similar in difficulty to the problem you will see on the final.
The problem is constructing a list of unique numbers from a list of numbers that may have duplicates in it. For this problem we are going to be working with a file containing 1000 random integers. The integers all fall in the range from 0 to 999. The list does contain duplicates, so our job will be to construct a list of the numbers in the file with duplicates removed from the list.
To demonstrate that most problems in computer science have more than one solution, I am going to construct three different solutions to this problem. In each solution I am going to construct a method that takes an array containing the original list of numbers as its parameter. The method will then construct and return an array containing the list of unique numbers.
The first solution starts with sorting the original list. With the original list of numbers sorted it will be much easier to find duplicates.
public static int[] removeDuplicates(int A[]) {
// Sort the list to make our work easier
Arrays.sort(A);
// Count the number of unique numbers in A
int count = 1;
for(int n = 1;n < A.length;n++) {
if(A[n-1] != A[n])
count++;
}
// Create the result array, and copy numbers over to it.
int B[] = new int[count];
B[0] = A[0];
int k = 1;
for(int n = 1;n < A.length;n++) {
if(A[n-1] != A[n]) {
B[k] = A[n];
k++;
}
}
return B;
}
A key part of the logic here is searching for new numbers. We will know that we have encountered a new number in the sorted list whenever we come across a number that is different than the number that came before it. We use this logic first to get a count of the unique numbers in A. Once we know this count we will know exactly how large the result array needs to be.
The second solution uses a completely different strategy. The second solution starts by collecting a count of how many times each of the possible numbers in A appears. Once we have collected that count information we can easily compute how many unique numbers are in A.
public static int[] removeDups(int A[]) {
// Collect information on how many times each of the
// numbers in A appears
int counts[] = new int[1000];
for(int n = 0;n < counts.length;n++)
counts[n] = 0;
for(int n = 0;n < A.length;n++)
counts[A[n]]++;
// Now use this count information to count how many unique
// numbers were in A
int count = 0;
for(int n = 0;n < counts.length;n++)
if(counts[n] > 0)
count++;
// Construct the result list and copy numbers over to it
int B[] = new int[count];
int k = 0;
for(int n = 0;n < counts.length;n++)
if(counts[n] > 0) {
B[k] = n;
k++;
}
return B;
}
The third solution makes use of a class from the Java class library. The TreeSet class has a useful property: it will refuse duplicates. In this solution we go through and add every number in A into a TreeSet. Because TreeSets refuse duplicates, we will end up with exactly one copy of each number from A in the TreeSet. All we have to do then is copy the numbers from the TreeSet back into an array.
public static int[] removeDupsWithSet(int A[]) {
TreeSet<Integer> set = new TreeSet<Integer>();
for(int n = 0;n < A.length;n++)
set.add(A[n]);
int B[] = new int[set.size()];
int k = 0;
for(int x : set) {
B[k] = x;
k++;
}
return B;
}