Detecting duplicates is part of a collection of standard algorithms.
Detecting duplicates means determining if an array contains at least one value more than once.
Unsorted array
For an array not known to be sorted, each value is checked against each subsequent value.
Algorithm
Loop through every value, excluding the last.
Loop through every value after the value from the outer loop.
If the values match
Return true.
Return false.
Implementation in Java
public static boolean hasDuplicate(int[] vals)
{
for(int i = 0; i < vals.length - 1; i++)
{
for(int j = i + 1; j < vals.length; j++)
{
if(vals[i] == vals[j])
return true;
}
}
return false;
}
Skipping the last element in the outer loop is not strictly required. If the outer loop is allowed to run up to and including the last element, the inner loop will not run when the outer loop visits the last element.
The inner loop cannot skip the last element.
Alternate algorithm
Loop through every value.
Loop through every value.
If the indexes are different and the values match
Return true.
Return false.
Alternate implementation
public static boolean hasDuplicate(int[] vals)
{
for(int i = 0; i < vals.length; i++)
{
for(int j = 0; j < vals.length; j++)
{
if(i != j && vals[i] == vals[j])
return true;
}
}
return false;
}
As in the previous algorithm, the outer loop can skip the last element if desired. The inner loop cannot skip the last element.
Sorted array
If an array is known to be sorted, detecting duplicates can be done more easily and much more efficiently.
The sort order (ascending vs descending) doesn’t matter. Duplicate values will be in adjacent positions in the array. The algorithm works as long as all duplicate values are adjacent, regardless of whether the values are actuall in order.
Algorithm
Loop through the array, excluding the first value.
If the current value matches the value immediately before it
Return true.
Return false.
Implementation in Java
public static boolean hasDuplicateSorted(int[] vals)
{
for(int i = 1; i < vals.length; i++)
{
if(vals[i - 1] == vals[i])
return true;
}
return false;
}
When skipping one or more elements, my preference is to start the loop later rather than end it earlier. This avoids the somewhat odd condition i < vals.length - 1 in the alternate solution below.
Alternate loop
public static boolean hasDuplicateSorted(int[] vals)
{
for(int i = 0; i < vals.length - 1; i++)
{
if(vals[i] == vals[i + 1])
return true;
}
return false;
}
Some programmers prefer to skip the last value instead of the first. In this case, the values at indexes i and i + 1 are checked.
Help & comments
Get help from AP CS Tutor Brandon Horn