creating an algorithm to find repeating values of an array

Question

I made a pseudo code algorithm to find repeating values of an array which includes float numbers:

mergeSort(A);  
int i <- 0
for i<- A.lenght-1
  if Arr[i] == A[i+1]
          return A[i]
          while A[i] = A[i+1]
                i++
else
    i++

I want to change the above algorithm to find the repeating values and the number of times they repeat. I have created the following algorithm:

mergeSort(A); 
HashMap hashMap;
Int result <-0 int i <- 0
for i<- A.lenght-1
    int j <- 0
    if A[i] == A[i+1]
          j <- j+1
          result <- A[i]
          while A[i] == A[i+1]
             i <- i+1
             j<- j+1
         hashMap.insert(result , j)
      else
         i++
return hashMap

Is this an efficient algorithm? Is it a good way to use a hashmap?

gevorg · Accepted Answer · 2016-06-19 18:26:44Z

1

You can simply use HashMap and do something like this:

HashMap hash;
for (int i = 0; i < A.lenght; i++){
    value = hash.get(A[i]); 
    if (value == null) // is the first time that we find A[i]
        hash.put(A[i], 1);
    else    // A[i] is a duplicate
        hash.put(A[i], value + 1);
}

avarage case = O(n)

I agree with pboulanger: pay attention to floating-point comparison.

edited Jun 19, 2016 at 18:26

gevorg

5,1155 gold badges40 silver badges54 bronze badges

answered Nov 16, 2010 at 22:18

SuperJulietta

6,8211 gold badge17 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Elton.fd Over a year ago

thats great, thanks. but, does hashmap accept float as a key? isnt there ant constraint for hashmap only to accept integers as keys?

Elton.fd Over a year ago

does data structure HashTable has the method get(key)- that you have use above - too?

SuperJulietta Over a year ago

Sandra you can use float, but you have to use wrapper class. Here are all methods supported download.oracle.com/javase/1.4.2/docs/api/java/util/… . Anywhere if you know how HashMap works, you can implement your own HashMap.

pboulanger · Accepted Answer · 2010-11-16 14:37:19Z

1

Be careful, the floating-point numbers are not exact types and the equal operator could return wrong values. For floating-point values prefer a test |f1-f2|

answered Nov 16, 2010 at 14:37

pboulanger

411 bronze badge

Comments

Andreas Brinck · Accepted Answer · 2010-11-16 12:15:31Z

0

Another option would be to store the result in an ArrayList of [value count] pairs, this is probably slightly more effective, there's really no need for a HashMap here. I know practially nothing about java, but you should be able to write something like:

arrayList.add(new Pair(result, j));

edited Nov 16, 2010 at 12:15

answered Nov 16, 2010 at 11:48

Andreas Brinck

52.9k15 gold badges87 silver badges114 bronze badges

6 Comments

Elton.fd Over a year ago

How can I insert pairs into ArrayList? arrayList arr;

Elton.fd Over a year ago

how about an HashTable? Isnt it better that I use it?

Andreas Brinck Over a year ago

A hashmap is useful when you need to do fast lookups in a table with "random" indices. What you're doing here is inserting numbers in a well defined order so there's really no need for a hash map.

Elton.fd Over a year ago

does it differ if I want to find duplicate i an array which includes integer numbers? should I use arayList for integers too?

Saeed Amiri Over a year ago

@Andreas Brinck, Array List is not efficient in all, It's better to use list or array or other generic collections not array list.

|

Collectives™ on Stack Overflow

creating an algorithm to find repeating values of an array

3 Answers 3

3 Comments

Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related