Your current algorithm works in O(n2) worst case. This can trivially be made to be O(n) at the cost of some memory using the algorithm described in this StackOverflow answer StackOverflow answer.
Your current algorithm works in O(n2) worst case. This can trivially be made to be O(n) at the cost of some memory using the algorithm described in this StackOverflow answer.
Your current algorithm works in O(n2) worst case. This can trivially be made to be O(n) at the cost of some memory using the algorithm described in this StackOverflow answer.
- 574
- 4
- 13
import java.util.BitSet;Set;
import java.util.HashSet;
public static boolean distinctValues(int[] arr){
BitSetSet<Integer> foundNumbers = new BitSetHashSet<Integer>();
for (int num : arr) {
if(foundNumbers.getcontains(num)){
return false;
}
foundNumbers.setadd(num);
}
return true;
}
I originally used a BitSet instead of a HashSet. While BitSet is generally more efficient, it does not support negative values. If you can guarantee that no values in the array will be negative, BitSet is still the better option.
import java.util.BitSet;
public static boolean distinctValues(int[] arr){
BitSet foundNumbers = new BitSet();
for (int num : arr) {
if(foundNumbers.get(num)){
return false;
}
foundNumbers.set(num);
}
return true;
}
import java.util.Set;
import java.util.HashSet;
public static boolean distinctValues(int[] arr){
Set<Integer> foundNumbers = new HashSet<Integer>();
for (int num : arr) {
if(foundNumbers.contains(num)){
return false;
}
foundNumbers.add(num);
}
return true;
}
I originally used a BitSet instead of a HashSet. While BitSet is generally more efficient, it does not support negative values. If you can guarantee that no values in the array will be negative, BitSet is still the better option.
Naming
tmp isn't the best names for the parameter because is not actually temporary - any changes made to the array inside that method will be reflected in the array outside the method. A better name would be nums or something similar.
A method called distinctValues should not return true when there are duplicates so, the return statements should be swapped.
Convention
Instead of starting at arr.length - 1 and moving towards 0, a more common pattern for iterating over elements in a list in Java is starting at 0 and moving towards arr.length - 1:
for(int i=0; i < arr.length; i++){
in cases where you don't need to know what index you are currently examining and you do not need to modify the array it's prefered to use a for-each loop
for(int n : arr){
Algorithm
Your current algorithm works in O(n2) worst case. This can trivially be made to be O(n) at the cost of some memory using the algorithm described in this StackOverflow answer.
After the convention and naming changes above, your original code should look like this:
public static boolean distinctValues(int[] arr){
for (int i = 0 i < arr.length-1; i++) {
for (int j = i+1; j < arr.length; j++) {
if (arr[i] == arr[j]) {
return false;
}
}
}
return true;
}
and after implementing the new algorithm:
import java.util.BitSet;
public static boolean distinctValues(int[] arr){
BitSet foundNumbers = new BitSet();
for (int num : arr) {
if(foundNumbers.get(num)){
return false;
}
foundNumbers.set(num);
}
return true;
}
Generalization
If this is for an assignment that asks for this to be implemented for an int[], you can ignore this part but, it's always good to generalize methods as much as possible. In this case int[] can be generalized to Iterable<Object>. The downside of this is that you can't call it on an Array and more; you have to first do Arrays.asList(arr)
public static boolean distinctValues(Iterable<Object> objs){
Set<Object> foundObjects = new HashSet<>();
for(Object o : objs){
if(foundObjects.contains(o)){
return false;
}
foundObjects.add(o);
}
return true;
}