1

I know there are already similar questions (1, 2, 3) but they are all in Python and they do not fit what I need.

Given two sorted list, say 1, 6, 13, 21, 28 and 2, 15, 20. The indices, without repeating (unlike link 1 above), of the closest number in the first array are returned, in this case 0, 2, 3.

The tricky point is, in the case 1, 4, 66, 67, 68, 71 and 68, 68, 68, 82, 82, returning 2, 3, 4, 5, 1 is more preferable than 1, 2, 3, 4, 5.

It is possible that the length of the first list < the length of the second list. 1, 7, 11 and 6, 24, 28, 32, 34 should return 0, 1, 2, X, X, where X can be any integer other than 0, 1 and 2. (Both 0, 1, 2, -1, -1 and 0, 1, 2, 3, 4 are acceptable.)

Edit: Just swap the two lists and return 0, 1, 2.

Codes given in C-like languages or pseudocode is preferable.

Any idea better than a brute-force search?

Edit

The given examples may not be the best solutions, e.g. the final (struckthrough) example could return 1, 0, 2 (1, 0, 2, X, X) instead.

graphemecluster
  • 301
  • 1
  • 9

1 Answers1

0

Let the first array be a and the second be b.

Let the cost of assigning index i to b[j] be abs(a[i] - b[j]). Then we can find a solution by modelling our problem as an unbalanced assignment problem in O(nr2) time where r is the size of the smallest array and n the biggest.

orlp
  • 112,504
  • 36
  • 218
  • 315
  • Great. But I may get `0, 2, 1, X, X` instead of `0, 1, 2, X, X` in the final example because both results cost the same. (When I use the squared distance instead, the second example got wrong.) Can you give a sample code in C#? Is there any method that does not require a cubic time complexity? – graphemecluster Mar 15 '21 at 05:10