CODEWITHSUNDEEP
javaarraysinteger
Asker
Asker

Reputation: 431

Find the two most similar values in an array (Java)

I have an array of integers and I want to find the two most similar values (least difference).

Example: if the values in the array are 80,100,500,600,501,505, The two most similar values are 500 and 501. How can I do this?

Upvotes: 4

Views: 2282

Answers (4)

Peter Lawrey
Peter Lawrey

Reputation: 533520

If you sort the data, the time complexity is O(N * ln(N))

int[] ints = {80, 100, 500, 600, 501, 505};
Arrays.sort(ints);
int value = 0, delta = Integer.MAX_VALUE;
for (int i = 0; i < ints.length - 1; i++) {
    int d = ints[i + 1] - ints[i];
    if (d < delta) {
        delta = d;
        value = ints[i];
    }
}
System.out.printf("value " + value + " and " + (value + delta));

prints

value 500 and 501

Upvotes: 2

MrYo
MrYo

Reputation: 1817

That seems small task, we can solve this problem as:

1: Apply any efficient sorting algorithm.

2:Then compare adjacent element and pick up whose difference is less.

code is here:

void nearestFinder(){
   int array[];
//apply  sorting algorithm - say selection sort
pre_diff = 0;
new_array = selection_sort(array);
   for(int i =0;i<new_array.length();i++){
      diff = Math.abs(new_array[i]-new_array[i+1]);
      if(diff>pre_diff){
       index =i;
       pre_diff =diff;
       }

      }
print(new_array[index],new_array[index+1])
}

Upvotes: 4

Colin D
Colin D

Reputation: 5661

The trick to this problem is sorting the array first. This will make it so you only need to compare numbers that are adjacent to each other; selecting the 2 that have the smallest difference.

psuedocode:

sort the array: use Arrays.sort()
 int max_difference = Integer.MAXVALUE
int val1, val2;
for(i=0; i< array_size -1; ++i) {
 int x = array[i+1] - array[i];
 if(x <= max_difference) {
   max_difference = x;
   val1 = array[i];
   val2 = array[i+1];
 }
}

at the end, val1 and val2 will contain the 2 most similiar values.

Upvotes: 3

mjgpy3
mjgpy3

Reputation: 8947

I would loop through each element O(N^2). To find the two most similar elements use subtraction and compare the difference with a stored lowest difference. Then once the lowest difference is found (ignoring the number in question you are searching for) you can also store the number you are searching with and the one you subtracted it from. You should also use absolute value so that the magnitude of the number is what you are comaring.

Upvotes: 0

Related Questions