0

我正在寻找一种方法来上下移动二维数组中的所有元素,以便满足特定条件的元素留在数组的末尾。我的意思的简化示例:

一个用 1 填充的 2D 整数数组,有四个 0。

1 1 1 1 1  
1 1 1 1 0  
1 1 1 0 1  
1 1 1 1 1  
0 0 1 1 1 

我想要做的是通过移动其他元素来填充孔(零),最后留下零。期望的结果是:

1 1 1 1 1  
1 1 1 1 1  
1 1 1 1 1  
1 1 1 1 1  
1 0 0 0 0

在我的项目中,我正在处理一个二维对象数组,其状态是决定移位的因素。我只是在寻找一个可以完成这个结果的基本算法。是否有捷径可寻?

4

7 回答 7

2

遍历数组并计数零。每次找到零时,将 1 添加到计数器并用 1 替换零。然后从数组的末尾到其开头,将 N 个位置替换为 0,其中 N 是零的总数。

于 2013-04-09T11:11:00.380 回答
0

对第一个数组中的每个数组进行冒泡排序,并按您的顺序对它们进行排序

for (i=0; i<array1.length; i++){
   yourBubblesort(array1[i]);
}

实现冒泡排序很容易,你必须在功课中做一些事情

于 2013-04-09T11:10:36.077 回答
0

试试这个方法

public void shiftZeros(int[] arr )
{
int count;
for(int j=0;j<arr.length-1;j++)
{
  if(arr[j]=0)
   {
    arr[j]=1;
    count++;
   }
}

for(int j=arr.length-1,i=1;i<count;i++,j--)
{
   arr[j]=0;
}

}
于 2013-04-09T11:18:38.553 回答
0

这是一种使用复制到新数组的方法

  • 创建新数组以保存移位元素/最终结果
  • 遍历数组
  • 复制一个元素,女巫将被移动(满足条件)到新数组中的最后一个空闲位置
  • 将不移动(不满足条件)的元素复制到数组中的下一个空闲位置

当元素即将遇到处理结束时,不会有重叠。

编辑

只是为了完整起见,这里是上面算法的一个实现

private E[][] shift(E[][] input) {
    int maxLen = get2DMaxLen(input);
    int i_next = 0, j_next = 0;
    int i_least = input.length-1, j_least = maxLen-1;
    E[][] actual = new E[input.length][maxLen];
    for(int i = 0; i < input.length; i++) {
        for(int j = 0; j < input[i].length; j++) {
            if(meetsCondition(input[i][j])) {
                actual[i_least][j_least--] = input[i][j];
                if(j_least == -1) {
                    j_least = maxLen-1;
                    i_least--;
                }
            } else {
                actual[i_next][j_next++] = input[i][j];
                if(j_next == input[i].length) {
                    j_next = 0;
                    i_next++;
                }
            }
        }
    }
    return actual;
}

测试输入

0 1 1 0 1 
0 1 1 1 0 
1 0 1 0 1 
1 1 0 1 1 
0 0 1 1 1 

输出

1 1 1 1 1 
1 1 1 1 1 
1 1 1 1 1 
1 0 0 0 0 
0 0 0 0 0
于 2013-04-09T11:34:39.707 回答
0

低效版本:

  • 遍历存储所有非 0 项的数组(例如,使用queue ,可以使用LinkedList进行模拟)。

  • 再次迭代,只需将存储的项目一一拉入数组

迭代器通过类似的东西:

for (int i = 0; i < arr.length; i++)
for (int j = 0; j < arr[i].length; j++)
  ...

更(空间)效率更高的版本:

同时遍历数组两次,读取每个值并将它们放在正确的位置。

伪代码:(希望足够可读)

while ahead.hasNext
  // skip all 0s
  do
    i = ahead.next
  while i == 0
  behind.writeNext(i)

// the rest must all be 0
while behind.hasNext
  behind.writeNext(0)

我不能给你代码,因为我不能为你做所有的工作。

于 2013-04-09T11:35:15.187 回答
0

为什么不对列进行降序排序,然后对每一行进行降序排序?有很多算法可以做到这一点。

于 2013-04-09T11:42:43.977 回答
0

对于上面的确切问题,解决方案可以是:

从两个指针开始,一个在数组的左上角,一个在右下角。让我们分别调用这些第一个和第二个指针。现在使用第一个指针逐行遍历数组。当您找到要放在末尾的元素(在这种情况下为“0”)时,请检查第二个元素指向的元素。如果第二个元素是 0,则递减第二个指针以指向二维数组中的倒数第二个元素。现在检查这个元素,如果这也是“0”,再次递减第二个指针,依此类推,直到达到“1”(必须在数组开头的元素)。然后交换两个元素。在任何时间点,如果指针相互交叉,则数组已按要求排序。

以下 java 代码将执行此操作:最初变量 endi 和 endj 指向最后一个元素(第二个指针),变量 i 和 j 指向第一个元素(第一个指针)。数组大小为 m X n。

for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            if(a[i][j]==0)
            { 
                while(a[endi][endj]!=1 && i*m+j<endi*m+endj) //second part of the condition checks if i,j and endi,endj haven't crossed over
                {
                    endj--;
                    if(endj==-1)
                    {
                        endj=n-1;
                        endi--;
                        if(endi==-1)
                        {
                            disparr(a,m,n);
                            System.exit(0);
                        }
                    }
                }
                if(!(i*m+j<endi*m+endj))//if the pointer have crossed over
                {
                    disparr(a,m,n);
                    System.exit(0);
                }    
                int t=a[i][j];
                a[i][j]=a[endi][endj];
                a[endi][endj]=t;

            }
        }
    }

对上述代码的其他改进可能是可能的,例如删除用于递减指向函数的指针并调用它的代码。但是代码可以正常工作。

于 2013-04-09T12:28:52.040 回答