向左移动元素N步(挑战) [英] Move elements N steps to the left (challenge)

问题描述

让我们说我们有这个数组:

Lets say we have this array:

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

然后我已经制作了一种将元素推到左侧并将所有null保留在右侧的方法:

Then I already made a method to push elements to the left and leaving all the nulls at the right:

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};

我知道可以通过创建相同大小的数组并循环遍历原始数组，然后将其分配给当前索引处的新索引(如果不为null)来简化操作.但是，我选择了更多的复杂性，因此对于真正的大型阵列来说，效率更高.

I know it could be done more simple with making an array of the same size and looping over the original and assign to the new one at the current index if not null. However I choose for a bit more complexity so it's more efficient for really large array.

虽然效果很好，但我有另一个想法.我一直在尝试解决该算法，但它正在杀死我. 这个想法如下:

While this works great I had another idea. I have been trying to solve the algorithm but it's killing me. The idea follows:

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

We start with this array again:

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

我要添加"m"，"o"添加数组的末尾.为此，我想再次将元素向左移动以腾出空间，但只增加腾出空间所需的数量. 因此，如果最后有2个null导致出现以下情况，我们就可以停止:

I want to add "m" and "o" add the end of the array. To do that I want to shift the elements to the left again to make room but only as many as required to make room. So we can stop once we have 2 nulls at the end resulting in:

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

挑战来了:

• 从右到左工作
• 直接将元素移动到右侧，因此我们无需将"l"向左移动一个，然后再向左移动一个，而是一步一步将其移动了2个索引.
• 不要使用新的数组，只能使用尽可能小的缓冲区
• (简而言之是有效的)

• work from right to left
• move elements directly to the right place, so instead of moving "l" one to the left and then one more time one to the left we move it 2 indexes in 1 step.
• don't use a new array, only a buffer that is as small as possible
• (in short be efficient)

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

So far I have failed multiple attempts. Below is my latest which probably won't help much. I hope someone can help with this interesting challenge.

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);应该起作用.)

(For this case, pushFromRightToLeft(1); pushFromRightToLeft(2); and pushFromRightToLeft(3); should work.)

推荐答案

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

You can go right to left, count nulls and when the wanted number of nulls is reached, go right again, moving the elements in place:

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);
}

此算法不需要额外的内存.用法:

This algorithm does not require additional memory. Usage:

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

这篇关于向左移动元素N步(挑战)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！