Given three arrays sorted in ascending order. Pull one number from each array to form a coordinate <x,y,z> in a 3Dspace. Find the coordinates of the points that is k-th closest to <0,0,0>.

We are using euclidean distance here.

Assumptions

• The three given arrays are not null or empty
• K > = 1 and K < = a.length * b.length * c.length

Return

• a size 3 integer list, the first element should be from the first array, the second element should be from the second array and the third should be from the third array

Examples

• A = {1, 3, 5}, B = {2, 4}, C = {3, 6}

• The closest is <1, 2, 3>, distance is sqrt(1 + 4 + 9)

• The 2nd closest is <3, 2, 3>, distance is sqrt(9 + 4 + 9)

Solution: 记得去重

  public List<Integer> closest(int[] a, int[] b, int[] c, int k) {
    boolean[][][] visited = new boolean[a.length][b.length][c.length];
    PriorityQueue<Node> pq = new PriorityQueue<>(1, new MyComparator());
    pq.offer(new Node(0, 0, 0, a[0] * a[0] + b[0] * b[0] + c[0] * c[0]));
    visited[0][0][0] = true;
    for (int i = 1; i < k; i++) {
      Node cur = pq.poll();
      if (cur.i + 1 < a.length && !visited[cur.i + 1][cur.j][cur.k]) {
        pq.offer(new Node(cur.i + 1, cur.j, cur.k, a[cur.i + 1] * a[cur.i + 1] + b[cur.j] * b[cur.j] + c[cur.k] * c[cur.k]));
        visited[cur.i + 1][cur.j][cur.k] = true;
      }
      if (cur.j + 1 < b.length && !visited[cur.i][cur.j + 1][cur.k]) {
        pq.offer(new Node(cur.i, cur.j + 1, cur.k, a[cur.i] * a[cur.i] + b[cur.j + 1] * b[cur.j + 1] + c[cur.k] * c[cur.k]));
        visited[cur.i][cur.j + 1][cur.k] = true;
      }
      if (cur.k + 1 < c.length&& !visited[cur.i][cur.j][cur.k + 1]) {
        pq.offer(new Node(cur.i, cur.j, cur.k + 1, a[cur.i] * a[cur.i] + b[cur.j] * b[cur.j] + c[cur.k + 1] * c[cur.k + 1]));
        visited[cur.i][cur.j][cur.k + 1] = true;
      }
    }
    List<Integer> ans = new ArrayList<>();
    ans.add(a[pq.peek().i]);
    ans.add(b[pq.peek().j]);
    ans.add(c[pq.peek().k]);
    return ans;
  }
  class Node {
    int i, j, k, distance;
    public Node(int i1, int i2, int i3, int dis) {
      i = i1;
      j = i2;
      k = i3;
      distance = dis;
    }
  }
  class MyComparator implements Comparator<Node> {
    public int compare(Node a, Node b) {
        return a.distance - b.distance;
    }
  }