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
-
What have you tried? Please take a look at item 3 of What topics can I ask about?.John Szakmeister– John Szakmeister2017-09-30 10:04:14 +00:00Commented Sep 30, 2017 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– Malcolm McLean2017-09-30 10:11:32 +00:00Commented Sep 30, 2017 at 10:11
-
Possible duplicate stackoverflow.com/questions/7055508/find-duplicates-in-an-arrayAvishek Bhattacharya– Avishek Bhattacharya2017-09-30 10:55:38 +00:00Commented Sep 30, 2017 at 10:55
-
1Possible duplicate of Find duplicates in an arrayAvishek Bhattacharya– Avishek Bhattacharya2017-09-30 10:56:00 +00:00Commented Sep 30, 2017 at 10:56
Add a comment
|
2 Answers
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.
Comments
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..
