找到你要的答案

Q:Reordering an array so that far apart elements are ordered first

Q:重新排序的数组元素是有序的,远第一

I have an array A of size n. I want to reorder the elements of A into another array B in such a way that elements that lie far apart in A are ordered first in B. For example, if n = 9, the two first elements of B should be A[0] and A[8], since these are the two elements furthest apart in A (distance 8). B[2] should be A[4], since that element is farthest from A[0] and A[8] (distance 4). Next we get B[3] = A[2] and B[4] = A[6], since A[2] and A[6] are farthest from A[0], A[4], and A[8] (minimum distance 2). Finally A[1], A[3], A[5], A[7] in the last four positions of B (minimum distance 1 from the already added elements).

What is a fast algorithm for doing this, and handling arrays for arbitrary size n?

我有一个数组的大小,我想再订购一个到另一个数组B这样的元素,李远在命令第一B.例如元素,如果n = 9,B两第一要素应该是[ 0 ]和[ 8 ],因为这是最远一个两元素(距离8)。B [ 2 ]应该是[ 4 ],因为该元素是最远的[ 0 ]和[ 8 ](距离4)。接下来,我们得到B [ 3 ] = A [ 2 ]和B [ 4 ] = [ 6 ],因为[ 2 ]和[ 6 ]是最远的[ 0 ],[ 4 ],和[ 8 ](最小距离)。最后A [ 1 ],[ 3 ],[ 5 ],[ 7 ]在过去的四个位置的B(从已添加的元素的最小距离1)。

什么是这样做的快速算法,并处理数组的任意大小n?

answer1: 回答1:

This will work for any arbitrary size. It uses a breadth first search http://en.wikipedia.org/wiki/Breadth-first_search

static List<Integer> maxDistance(int _start, int _end) {
  List<Integer> result = new ArrayList<>(Arrays.asList(_start, _end - 1));
  List<List<Integer>> ranges = Arrays.asList(Arrays.asList(_start + 1, _end - 1));

  while(!ranges.isEmpty()) {
    List<List<Integer>> ranges2 = ranges;
    ranges = new ArrayList<>();
    for(List<Integer> range: ranges2) {
      int start = range.get(0),
          end = range.get(1);
      if(end - start == 1) {
        result.add(start);
      } else if(end > start) {
        int mid = (start + end)/2;
        result.add(mid);
        ranges.add(Arrays.asList(start, mid));
        ranges.add(Arrays.asList(mid + 1, end));
      }
    }
  }

  return result;
}

这将适用于任意大小。它采用广度优先搜索http://en.wikipedia.org/wiki/breadth-first_search

static List<Integer> maxDistance(int _start, int _end) {
  List<Integer> result = new ArrayList<>(Arrays.asList(_start, _end - 1));
  List<List<Integer>> ranges = Arrays.asList(Arrays.asList(_start + 1, _end - 1));

  while(!ranges.isEmpty()) {
    List<List<Integer>> ranges2 = ranges;
    ranges = new ArrayList<>();
    for(List<Integer> range: ranges2) {
      int start = range.get(0),
          end = range.get(1);
      if(end - start == 1) {
        result.add(start);
      } else if(end > start) {
        int mid = (start + end)/2;
        result.add(mid);
        ranges.add(Arrays.asList(start, mid));
        ranges.add(Arrays.asList(mid + 1, end));
      }
    }
  }

  return result;
}
answer2: 回答2:

Something like this should do it: You copy the first element. Take the length of the array as a step size, and copy the odd multiples of this. Halve the step size, then repeat until all the elements have been copied (and the step size is 1). Implementing this in Java might look like this:

public static int[] farApartSort(int[] A) {

// Set up
int[] B = new int[A.length];
int i = 0;

// First value
B[i++] = A[0];

// Loop through the array in increments which halve each time
int chunkLength = A.length - 1;
do {
    // Take the odd multiples of the current increment
    for (int j = 1; chunkLength * j < A.length; j += 2) {
        // Copy the values into the sorted array
        B[i++] = A[chunkLength * j];
    }
    chunkLength /= 2;
} while (chunkLength > 0);

return B;

}

Something like this should do it: You copy the first element. Take the length of the array as a step size, and copy the odd multiples of this. Halve the step size, then repeat until all the elements have been copied (and the step size is 1). Implementing this in Java might look like this:

public static int[] farApartSort(int[] A) {

// Set up
int[] B = new int[A.length];
int i = 0;

// First value
B[i++] = A[0];

// Loop through the array in increments which halve each time
int chunkLength = A.length - 1;
do {
    // Take the odd multiples of the current increment
    for (int j = 1; chunkLength * j < A.length; j += 2) {
        // Copy the values into the sorted array
        B[i++] = A[chunkLength * j];
    }
    chunkLength /= 2;
} while (chunkLength > 0);

return B;

}

algorithm  sorting