我需要将数组中所有的0移动到数组的末尾。
例如：[1, 10, 0, 5, 7] 应该变为 [1, 10, 5, 7, 0]。
我可以使用正向循环或反向循环。
不能创建新的数组。
这是我目前的代码：
for (int i = arr.length; i <= 0; --i) {
if (arr[i] != 0) {
arr[i] = arr.length - 1;
}
}
谢谢！
将数组中的0移动到末尾
8
- Nobody
7
你有任何限制吗？ - dcow
1沿着走，如果你发现一个零后面不跟着另一个零，那就交换它们。重复此过程直到没有更多的交换... - Boris the Spider
冒泡排序？... - dcow
@Gary McSperry，您编辑了这个问题。您的意思是您无法创建一个新的循环吗？ - dcow
@DaidCowden 我的意思是我无法创建一个新数组，我的错。 - Nobody
显示剩余2条评论
22个回答
15
SIZE(n)，其中n = arr.size，保留顺序：
创建一个与需要从中删除0的初始数组相同大小的数组。迭代原始数组，并将每个元素添加到新数组中，前提是它不是0。当你遇到一个0时，计数它。现在，当你到达第一个数组的末尾时，只需将计算出的0的数量添加到数组末尾即可。更简单的是，由于Java会将数组初始化为0，因此您可以忽略在最后添加零。
编辑
由于您增加了不允许创建新数组的额外限制，因此我们需要采用与我上面建议的略有不同的方法。
SIZE(1)
我假设数组需要保持在移动0之前的顺序。如果不是这种情况，则有另一种简单的解决方案，如Brad的答案所述：将“最后一个零”索引初始化为数组的最后一个元素，然后向后迭代，在任何零和递减每次执行交换或查看零的最后一个零的索引。
SIZE(1)，保留顺序：
要将0移动到结尾而不重复数组并保持元素正确的顺序，您可以完全按照我建议的方法做，但不复制数组，而是在同一数组上保持两个索引。
从数组开始有两个索引。如果当前元素不为0，则不要将其复制到新数组中，而是将其留在原地并将两个索引都递增。当您到达一个零时，只递增一个索引。现在，如果两个索引不相同，并且您没有看到一个零，请将当前元素与已遇到的0位置的索引交换。在这两种情况下，只要当前元素不为0，就递增另一个索引。
操作将如下所示：
int max = arr.length;
for (int i = 0, int j = 0; j < max; j++) {
if (arr[j] != 0) {
if (i < j) {
swap(arr, i, j);
}
i++
}
}
在此运行：
{ 1, 2, 0, 0, 0, 3, 4, 0, 5, 0 }
产量:
{ 1, 2, 3, 4, 5, 0, 0, 0, 0, 0 }
我为任何对此感到好奇的人制作了完全运作版本。
- dcow
2
2一个新的int数组默认为0，因此您甚至不需要保持计数或初始化。 - jzworkman
在Java中是可以的。一开始我没有看到Java标签，以为这是C语言。我已经编辑了我的答案。 - dcow
6
有两种选择：
创建一个与当前数组大小相同的新数组，然后遍历您当前的数组并仅使用值填充新数组。然后用“零”填充新数组中的剩余条目。
不创建新数组，可以倒序遍历当前数组，当遇到“零”时将其与数组的最后一个元素交换。您需要计算已交换的“零”元素数量，以便在第二次交换时，您将与倒数第二个元素交换，以此类推。
[编辑] 7年后发布，以解决评论中留下的“排序”问题和“最后一个元素为零”的问题。
public class MyClass {
public static void main(String[] args) {
int[] elements = new int[] {1,0,2,0,3,0};
int lastIndex = elements.length-1;
// loop backwards looking for zeroes
for(int i = lastIndex; i >=0; i--) {
if(elements[i] == 0) {
// found a zero, so loop forwards from here
for(int j = i; j < lastIndex; j++) {
if(elements[j+1] == 0 || j == lastIndex) {
// either at the end of the array, or we've run into another zero near the end
break;
}
else {
// bubble up the zero we found one element at a time to push it to the end
int temp = elements[j+1];
elements[j+1] = elements[j];
elements[j] = temp;
}
}
}
}
System.out.println(Arrays.toString(elements));
}
}
为您提供了...
[1, 2, 3, 0, 0, 0]
- Brad
4
你能否更详细地说明一下选项2？抱歉，我非常新手。 - Nobody
2此解决方案不保留输入元素的顺序。 - user1772643
如果数组中的最后一个元素为0，则此解决方案将失败。 - Manisha
“ordering” 和 “如果最后一个元素是零怎么办” 的问题已经解决。 - Brad
2
基本解决方案是建立归纳假设，即子数组可以保持已解决状态。然后通过添加一个元素来扩展子数组并维护假设。在这种情况下，有两个分支 - 如果下一个元素为零，则不进行任何操作。如果下一个元素为非零，则将其与行中的第一个零交换。
不管怎样，在这个想法优化后的解决方案（虽然是用C#编写的）如下：
void MoveZeros(int[] a)
{
int i = 0;
for (int j = 0; j < a.Length; j++)
if (a[j] != 0)
a[i++] = a[j];
while (i < a.Length)
a[i++] = 0;
}
有一些思考可以引导我们得到这个解决方案，从归纳法解开始，可以正式证明其正确性。如果你感兴趣，可以查看完整分析：将零值移动到数组末尾
- Zoran Horvat
1
var size = 10;
var elemnts = [0, 0, 1, 4, 5, 0,-1];
var pos = 0;
for (var i = 0; i < elemnts.length; i++) {
if (elemnts[i] != 0) {
elemnts[pos] = elemnts[i];
pos++;
console.log(elemnts[i]);
}
}
for (var i = pos; i < elemnts.length; i++) {
elemnts[pos++] = 0;
console.log(elemnts[pos]);
}
- Tushar Budhe
1
1,4,5,-1,-5,8,0,0,0,0。 - Tushar Budhe
0
这是一种将零移动到数组末尾的方法。
public class SeparateZeroes1 {
public static void main(String[] args) {
int[] a = {0,1,0,3,0,0,345,12,0,13};
movezeroes(a);
}
static void movezeroes(int[] a) {
int lastNonZeroIndex = 0;
// If the current element is not 0, then we need to
// append it just in front of last non 0 element we found.
for (int i = 0; i < a.length; i++) {
if (a[i] != 0 ) {
a[lastNonZeroIndex++] = a[i];
}
}//for
// We just need to fill remaining array with 0's.
for (int i = lastNonZeroIndex; i < a.length; i++) {
a[i] = 0;
}
System.out.println( lastNonZeroIndex );
System.out.println(Arrays.toString(a));
}
}
这在Python中非常简单。我们将使用列表推导来完成它
a =[0,1,0,3,0,0,345,12,0,13]
def fix(a):
return ([x for x in a if x != 0] + [x for x in a if x ==0])
print(fix(a))
- Soudipta Dutta
0
public static void main(String[] args) {
Integer a[] = {10,0,0,0,6,0,0,0,70,6,7,8,0,4,0};
int flag = 0;int count =0;
for(int i=0;i<a.length;i++) {
if(a[i]==0 ) {
flag=1;
count++;
}else if(a[i]!=0) {
flag=0;
}
if(flag==0 && count>0 && a[i]!=0) {
a[i-count] = a[i];
a[i]=0;
}
}
}
- satish
0
这是我的代码，其中包含2个for循环：
int [] arr = {0, 4, 2, 0, 0, 1, 0, 1, 5, 0, 9,};
int temp;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] == 0)
{
for (int j = i + 1; j < arr.length; j++)
{
if (arr[j] != 0)
{
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
break;
}
}
}
}
System.out.println(Arrays.toString(arr));
输出：[4，2，1，1，5，9，0，0，0，0，0]
- A.Idrizi
0
int[] nums = { 3, 1, 2, 5, 4, 6, 3, 2, 1, 6, 7, 9, 3, 8, 0, 4, 2, 4, 6, 4 };
List<Integer> list1 = new ArrayList<>();
List<Integer> list2 = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 3) {
list1.add(nums[i]);
} else if (nums[i] != 3) {
list2.add(nums[i]);
}
}
List<Integer> finalList = new ArrayList<>(list2);
finalList.addAll(list1);
}
}
- Ostap_87
0
int[] nums = {3,1,2,5,4,6,3,2,1,6,7,9,3,8,0,4,2,4,6,4};
int i = 0;
for(int j = 0, s = nums.length; j < s;) {
if(nums[j] == 3)
j++;
else {
int temp = nums[i];
nums[i] = nums[j];``
nums[j] = temp;
i ++;
j ++;
}
}
- Ostap_87
0
这是我的实现方式。 时间复杂度：O(n)，空间复杂度：O(1) 以下是代码片段：
int arr[] = {0, 1, 0, 0, 2, 3, 0, 4, 0};
int i=0, k = 0;
int n = sizeof(arr)/sizeof(arr[0]);
for(i = 0; i<n; i++)
{
if(arr[i]==0)
continue;
arr[k++]=arr[i];
}
for(i=k;i<n;i++)
{
arr[i]=0;
}
output: {1, 2, 3, 4, 0, 0, 0, 0, 0}
解释：使用另一个变量k来保存索引位置，将非零元素向前移动并保持顺序。遍历数组后，非零元素被移到数组的前面，然后使用另一个循环从k开始覆盖剩余位置为零。
- paras_47
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接