-1

I need to find duplicate latitude in an array and nudge it a bit to avoid marker display problem.

I searched and find a way to do it in ruby:

1.find duplicate element in ruby (I consider sort array element and check adjacent element)

2.use array.indexof() to get its index(may have 3 or more duplicate element)

This works sure but I feel its not the best way. Is there a way to find duplicate and index of duplicate in one go?

Thanks in advance

EDIT: I've find a way,check duplicate and change on spot. But the problem is this function change all duplicate value to another duplicated value.

I think its because the main array is not updated during check and change procedure, attached is my code,anyway to improve it?

    @ln=0

     for @ln in 0..@checkLocation.length-1 do

     if (!(@checkLocation.index(@existlat)==nil) && (@existlat!=nil))   
     @checkLocation[@ln]=@checkLocation[@ln]+0.00001
     end
     @existlat=@checkLocation[@ln]
     end
ashisrai_
  • 6,438
  • 2
  • 26
  • 42
asdjkag
  • 448
  • 1
  • 7
  • 23
  • I don't think there is a non-expensive way to do this. Sorting and checking would work provided that you know you will only have ONE dupe. If you have more than one, you will have to check each element against all other elements. This can be slightly optimized. You will probably have to run an algorithm with a complexity close to O(n²). – victor Sep 17 '14 at 03:44
  • If you can use a secondary array to store the values you can achieve O(n) however. Example here: http://stackoverflow.com/questions/14944458/find-duplicate-element-in-array-in-time-on – victor Sep 17 '14 at 03:50
  • thank you bro.I'm shocked as I just learn O(n) algo and someone mention it in real life :D – asdjkag Sep 17 '14 at 03:53
  • I would like to emphasize that most of the O(n) algorithms for this won't work if the element of your array is bigger than the size of the array, because you will try to access a position that does not exist on the second array. Also they only work for integers, mostly – victor Sep 17 '14 at 03:56
  • you do not need the index of duplicate element,when you check and find it can just nudge it on the spot –  Sep 17 '14 at 04:08

2 Answers2

4
a = [:a, :b, :c, :b, :d, :a, :e]
a.each_index.group_by{|i| a[i]}.values.select{|a| a.length > 1}.flatten
# => [0, 5, 1, 3]
sawa
  • 165,429
  • 45
  • 277
  • 381
2

Finding dupes is not very difficult if performance is not a real issue for you. The most natural way would be to compare each element with all the other elements:

for (int i = 0; i < arraySize-1; ++i) {
    for (int j = i+1; j < arraySize; ++j) {
         if(array[i] == array[j]) changeDupe(array[j]);
    }
}

The code above will allow you to change all the dupes. Example in execution, changin dupes to 0:

Input:  {1, 2, 3, 2, 1, 4, 5, 6, 8, 2}
Output: {1, 2, 3, 0, 0, 4, 5, 6, 8, 0}

Another way to achieve this is to use a second array. If you are using integer values, you can make it like this:

int input[10] = {1, 2, 3, 2, 1, 4, 5, 6, 8, 2};
bool output[10] = {false, false, false, false, false, false, false, false, false, false};

for (int i = 0; i < arraySize; ++i) {
     if (output[input[i]] == false) changeDupe(input[i]));
     else output[input[i]] = true;
}

However, if one of your elements is bigger than the size of your array you will have a boundary problem. Suppose you have the value 100, then you would be trying to access the 100th element of the boolean array.

If you want to use the second algorithm but you are not working with an integer array, you could use a map to map each value on your array to an int, and then use the map value to set the booleans. A pseudocode would look like this:

 Map<yourData, int> map;
 map<someValue, 1>;
 map[someValue] = 1; //work based on this return value;

Yeeeet another way is to sort the array before iterating over it, and stop once you hit a different number. This would diminish the number of times you iterate over the array, but you would be adding the sorting algorithm complexity (probably O(n log(n))). The code would look something like this:

int i = 0;
while (i < arraySize-1) {

    if(array[i] == array[i+1])
        array[i] = 0;

    i++;
}

Input: {1, 1, 2, 3, 3, 4, 5, 6, 7, 8};
Output: {0, 1, 2, 0, 3, 4, 5, 6, 7, 8}

Complexity: for the first algorithm, you would have N*(N-1) which I would say is O(n²). for the second is O(n), but restrictions apply. for the third, it would be the sort + O(n) for the loop.

victor
  • 1,532
  • 1
  • 13
  • 32