The algorithm only need to detect if there are at least 2 number which are the same.
Is the one in my picture the best way to do it or is there a more effective way.
This is a task in a book and I don't no if i did it right.
Algorithm
Asked
Active
Viewed 56 times
0
-
What have you tried? Please take a look at item 3 of [What topics can I ask about?](https://stackoverflow.com/help/on-topic). – John Szakmeister Sep 30 '17 at 10:04
-
I assume the book is asking you to code that algorithm, which is two nested loops. Not the most efficient but straightforwards and workable. – Malcolm McLean Sep 30 '17 at 10:11
-
Possible duplicate https://stackoverflow.com/questions/7055508/find-duplicates-in-an-array – Avishek Bhattacharya Sep 30 '17 at 10:55
-
1Possible duplicate of [Find duplicates in an array](https://stackoverflow.com/questions/7055508/find-duplicates-in-an-array) – Avishek Bhattacharya Sep 30 '17 at 10:56
2 Answers
2
If the array is sorted:
for(int i=0; i<a.length-1; i++)
if(a[i]==a[i+1])
return true;
return false;
if the array is not sorted, use a cache:
boolean[] cache=new boolean[N];
Arrays.fill(cache,false); //set all values to false
for(int i=0; i<a.length; i++)
if(cache[a[i]])
return true;
else
cache[a[i]]=true; //mark element a[i] as seen
return false;
In the above, N is the maximum value that occurs in array a. If N is unknown or very large, or your array contains negative values, use a map instead of an array as cache.
Both solutions run in O(n) time. The second solution just needs an external cache to remember which elements we've seen before.
Joris Kinable
- 2,232
- 18
- 29
0
Can you just do:
Loop on I
Loop on j
If value of a[I] = value of a[j]
Break; /*at least one double found*/
No?
Wrong.. Forget about it..
Totoc1001
- 338
- 2
- 11