将元素向左移动 N 步（挑战）

Question

假设我们有这个数组：

{"a", "b", "c", "d", null, "f", "g", null, "i", "j", "k", null, "l"};

然后我已经做了一个方法把元素推到左边，把所有的空值都留在右边：

void pushFromLeftToLeft() {

  int nullCount = 0;

  for (int i = 0; i < BUCKET_CAPACITY; i++) {
      if (data[i] == null) {
        nullCount++;
      }
      else if (nullCount != 0) {
        data[i-nullCount] = data[i];
      }
  }
  // set the last elements to null 
  for (int i = BUCKET_CAPACITY - nullCount; i < BUCKET_CAPACITY; i++) {
     data[i] = null;  
  }

}

这导致：

{"a", "b", "c", "d", "f", "g", "i", "j", "k", "l", null, null, null};

我知道可以更简单地制作一个相同大小的数组并遍历原始数组并在当前索引处分配给新数组（如果不为空）。但是我选择了稍微复杂一点的，所以它对于真正的大数组更有效。

虽然这很有效，但我有另一个想法。我一直在尝试解决该算法，但它让我丧命。思路如下：

我们再次从这个数组开始：

{"a", "b", "c", "d", null, "f", "g", null, "i", "j", "k", null, "l"};

我想添加"m"和"o"添加数组的末尾。为此，我想再次将元素向左移动以腾出空间，但只需要腾出空间所需的数量即可。所以我们可以在最后有 2 个空值时停止，结果是：

{"a", "b", "c", "d", null, "f", "g", "i", "j", "k", "l", null, null};

挑战来了：

从右到左工作
将元素直接移动到正确的位置，所以我们一步移动 2 个索引，而不是向左移动 "l" 一个然后再向左移动一个。
不使用新数组，只使用尽可能小的缓冲区
(简而言之要有效率)

到目前为止，我已经多次尝试失败。以下是我的最新消息，可能不会有太大帮助。我希望有人能帮助解决这个有趣的挑战。

String[] data = new String[] {"a", "b", "c", "d", null, "f", "g", null, "i", "j", "k", null, "l"};
int BUCKET_CAPACITY = data.length;

void pushFromRightToLeft(int offset) {

  int currentOffset = offset; // if we find a null this decreases

  Object[] buffer = new Object[offset];

  {
    int bufferIndex1 = (BUCKET_CAPACITY-1) % buffer.length;
    buffer[bufferIndex1] = data[BUCKET_CAPACITY-1];
  }


  for (int i = BUCKET_CAPACITY-1; i >= offset; i--) {

    int bufferIndex1 = i % buffer.length;
    int bufferIndex2 = (i+1) % buffer.length;

    if (buffer[bufferIndex1] == null) {
      //nullCount++;
      currentOffset--;
      // what to do, we don't want to move the null forward...
      // move last buffered item into this place
      data[i] = (String) buffer[bufferIndex2];
    } 
    else {

      buffer[bufferIndex2] = data[i-currentOffset]; 
      data[i-currentOffset] = (String) buffer[bufferIndex1]; 

      if (currentOffset == 0) {
        println("break on: "+i);
        break;
      }

    }

  } 

}

（对于这种情况，pushFromRightToLeft(1); pushFromRightToLeft(2); 和 pushFromRightToLeft(3); 应该有效。）

Answer 1

您可以从右到左计算空值，当达到所需的空值数量时，再次向右移动元素：

public static void moveNulls(Object[] arr, int howMany) {
    int offset = arr.length;
    int nullCount = 0;
    while(nullCount < howMany) {
        if(arr[--offset] == null)
            nullCount++;
        if(offset == 0 && nullCount < howMany)
            throw new IllegalStateException("Not enough nulls");
    }
    int target = offset;
    while(offset < arr.length) {
        if(arr[offset] != null)
            arr[target++]=arr[offset++];
        else
            offset++;
    }
    Arrays.fill(arr, target, offset, null);
}

该算法不需要额外的内存。用法：

for(int i=0; i<5; i++) {
    String[] arr = {"a", "b", "c", "d", null, "f", "g", null, "i", "j", "k", null, "l"};
    moveNulls(arr, i);
    System.out.println(Arrays.toString(arr));
}

输出：

[a, b, c, d, null, f, g, null, i, j, k, null, l]
[a, b, c, d, null, f, g, null, i, j, k, l, null]
[a, b, c, d, null, f, g, i, j, k, l, null, null]
[a, b, c, d, f, g, i, j, k, l, null, null, null]
Exception in thread "main" java.lang.IllegalStateException: Not enough nulls

Answer 2

纯为未优化算法：

List<String> shiftInFromRight(String[] data, List<String> inserts) {
    for (int i = data.length - 1; i >= 0 && !inserts.isEmpty(); --i) {
         String old = data[i];
         data[i] = inserts.remove(inserts.size() - 1);
         if (old != null) {
             inserts.add(0, old);
         }
    }
    return inserts; // The overflow if any.
}

要插入的东西可以是一个数组（它只会收缩，所以额外的round-robin计数器就足够了）。给定 nullCounter，不需要产生溢出。

void shiftInFromRight(String[] data, String[] inserts) {
    final int N = inserts.length;
    int n = N;
    int right = n;
    for (int i = data.length - 1; i >= 0 && n > 0; --i) {
         String old = data[i];
         --n;
         --right;
         if (right < 0) { // Round-robin.
             right += n;
         }
         data[i] = inserts[right];
         if (old != null) {
             inserts[right] = old;
             ++n;
         }
    }
    if (n > 0) {
        throw new OutOfMemoryException(); // joke
    }
}

Answer 3

这是我的结果。

一定要看看 Tagir Valeev 的解决方案，速度稍快！使用此解决方案，缓冲区会增加很多时间。

void moveNulls(Object[] data, int howMany) {

  if (howMany == 0) return;

  Object[] buffer = new Object[howMany*2];
  int b_getIndex = 0;
  int b_setIndex = howMany;

  int nullCount = 0;


  for (int i = data.length-1; i >= howMany; i--) {

    if (data[i] == null) {
      nullCount++;
    }
    else {
      buffer[b_setIndex] = data[i];
      b_setIndex++;
    }

    data[i] = buffer[b_getIndex];

    b_getIndex++;
    if (b_setIndex == buffer.length) b_setIndex = 0; 
    if (b_getIndex == buffer.length) b_getIndex = 0;

    if (nullCount == howMany) break;
  } 

}

将元素向左移动 N 步（挑战）

Move elements N steps to the left (challenge)

java

arrays

algorithm

pseudocode