我需要将数组中的所有 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;
}
}
谢谢！
问问题
33047 次
22 回答
15
SIZE(n) 其中 n = arr.size，保留排序：
创建一个与需要从中删除 0 的初始数组大小相同的数组。遍历原始数组并将每个元素添加到新数组中，前提是它不为 0。当遇到 0 时，计算它。现在，当您到达第一个数组的末尾时，只需将计数的 0 数添加到数组的末尾即可。而且，更简单的是，由于 Java 将数组初始化为 0，因此您可以忘记在末尾添加零。
编辑
由于您添加了无法创建新数组的附加约束，因此我们需要采用与我上面建议的方法稍有不同的方法。
尺寸(1)
我假设数组需要保持与将 0 移到末尾之前的顺序相同。如果不是这种情况，还有另一个简单的解决方案，如 Brads 回答中所述：初始化数组的最后一个元素的“最后一个零”索引，然后向后迭代将任何零与最后一个零的索引交换，每次递减您执行交换或看到零。
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 }
我为任何好奇的人制作了一个完整的版本。
于 2013-04-01T19:34:39.890 回答
6
想到两个选择
创建一个相同大小的新数组，然后迭代当前数组并仅用值填充新数组。然后用“零”填充新数组中的剩余条目
在不创建新数组的情况下，您可以向后迭代当前数组，并在遇到“零”时将其与数组的最后一个元素交换。您需要记录交换的“零”元素的数量，以便在第二次交换时与
last-1元素交换，依此类推。
[编辑]最初发布以解决评论中留下的“排序”问题和“最后一个元素为零”问题 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]
于 2013-04-01T19:37:29.453 回答
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;
}
从可以正式证明正确的归纳解决方案开始，有一些思考导致了这个解决方案。如果你有兴趣，整个分析在这里：将零值移动到数组的末尾
于 2015-06-11T13:34:10.567 回答
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]);
}
于 2016-07-06T18:58:43.353 回答
0
int arrNew[] = new int[arr.length];
int index = 0;
for(int i=0;i<arr.length;i++){
if(arr[i]!=0){
arrNew[index]=arr[i];
index++;
}
}
由于 int 的数组被初始化为零（根据语言规范）。这将产生您想要的效果，并将按顺序向上移动其他所有内容。
编辑：根据您不能使用新数组的编辑，此答案不满足您的要求。相反，您需要检查零（从数组的末尾开始并一直工作到开头）并与数组的最后一个元素交换，然后减少最后一个非零元素的索引，然后您将与下一个交换. 前任：
int lastZero = arr.length - 1;
if(arr[i] == 0){
//perform swap and decrement lastZero by 1 I will leave this part up to you
}
于 2013-04-01T19:34:49.760 回答
0
/// <summary>
/// From a given array send al zeros to the end (C# solution)
/// </summary>
/// <param name="numbersArray">The array of numbers</param>
/// <returns>Array with zeros at the end</returns>
public static int[] SendZerosToEnd(int[] numbersArray)
{
// Edge case if the array is null or is not long enough then we do
// something in this case we return the same array with no changes
// You can always decide to return an exception as well
if (numbersArray == null ||
numbersArray.Length < 2)
{
return numbersArray;
}
// We keep track of our second pointer and the last element index
int secondIndex = numbersArray.Length - 2,
lastIndex = secondIndex;
for (int i = secondIndex; i >= 0; i--)
{
secondIndex = i;
if (numbersArray[i] == 0)
{
// While our pointer reaches the end or the next element
// is a zero we swap elements
while (secondIndex != lastIndex ||
numbersArray[secondIndex + 1] != 0)
{
numbersArray[secondIndex] = numbersArray[secondIndex + 1];
numbersArray[secondIndex + 1] = 0;
++secondIndex;
}
// This solution is like having two pointers
// Also if we look at the solution you do not pass more than
// 2 times actual array will be resume as O(N) complexity
}
}
// We return the same array with no new one created
return numbersArray;
}
于 2016-03-25T19:17:46.153 回答
0
如果问题添加以下条件。
- 时间复杂度必须为 O(n) - 您只能迭代一次。
- 额外的空间复杂度必须为 O(1) - 您不能创建额外的数组。
然后以下实施将正常工作。
要遵循的步骤：
- 遍历数组并维护非零元素的计数。
- 每当我们遇到放在数组中计数位置的非零元素时，也会增加计数。
- 一旦数组被完全迭代，将零放在数组的末尾，直到计数达到数组的原始长度。
public static void main(String args[]) { int[] array = { 1, 0, 3, 0, 0, 4, 0, 6, 0, 9 }; // Maintaining count of non zero elements int count = -1; // Iterating through array and copying non zero elements in front of array. for (int i = 0; i < array.length; i++) { if (array[i] != 0) array[++count] = array[i]; } // Replacing end elements with zero while (count < array.length - 1) array[++count] = 0; for (int i = 0; i < array.length; i++) { System.out.print(array[i] + " "); } }
于 2016-12-02T10:38:08.567 回答
0
时间复杂度 = O(n)，空间复杂度 = O(1)
import java.util.Scanner;
public class ShiftZeroesToBack {
int[] array;
void shiftZeroes(int[] array) {
int previousK = 0;
int firstTime = 0;
for(int k = 0; k < array.length - 1; k++) {
if(array[k] == 0 && array[k + 1] != 0 && firstTime != 0) {
int temp = array[previousK];
array[previousK] = array[k + 1];
array[k + 1] = temp;
previousK = previousK + 1;
continue;
}
if(array[k] == 0 && array[k + 1] != 0) {
int temp = array[k];
array[k] = array[k + 1];
array[k + 1] = temp;
continue;
}
if(array[k] == 0 && array[k + 1] == 0) {
if(firstTime == 0) {
previousK = k;
firstTime = 1;
}
}
}
}
int[] input(Scanner scanner, int size) {
array = new int[size];
for(int i = 0; i < size; i++) {
array[i] = scanner.nextInt();
}
return array;
}
void print() {
System.out.println();
for(int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println();
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
ShiftZeroesToBack sztb = new ShiftZeroesToBack();
System.out.print("Enter Size of Array\t");
int size = scanner.nextInt();
int[] input = sztb.input(scanner, size);
sztb.shiftZeroes(input);
sztb.print();
}
}
于 2017-04-06T19:29:26.863 回答
0
假设我们有一个数组
[5,4,0,0,6,7,0,8,9]
假设我们有 0-100 之间的数组元素，现在我们的目标是移动数组末尾的所有 0。现在从数组中保存 0 并用非零元素检查它，如果发现任何非零元素与该元素交换，依此类推，在循环结束时，我们将找到解决方案。
这是代码
for (int i = 0; i < outputArr.length; i++)
{
for (int j = i+1; j < outputArr.length; j++)
{
if(outputArr[i]==0 && outputArr[j]!=0){
int temp = outputArr[i];
outputArr[i] = outputArr[j];
outputArr[j] = temp;
}
}
print outputArr[i]....
}
输出：
[5,4,6,7,8,9,0,0,0]
于 2017-10-14T17:09:54.303 回答
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 开始的另一个循环用于用零覆盖剩余位置。
于 2017-11-05T12:30:18.220 回答
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]
于 2018-02-13T21:07:19.590 回答
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))
于 2018-03-26T06:48:49.120 回答
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;
}
}
}
于 2018-03-30T19:19:18.553 回答
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);
}
}
于 2018-09-02T15:32:38.600 回答
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 ++;
}
}
于 2018-09-02T15:58:49.073 回答
0
对于Integer数组，它可以很简单
Integer[] numbers = { 1, 10, 0, 5, 7 };
Arrays.sort(numbers, Comparator.comparing(n -> n == 0));
对于int数组：
int[] numbers = { 1, 10, 0, 5, 7 };
numbers = IntStream.of(numbers).boxed()
.sorted(Comparator.comparing(n -> n == 0))
.mapToInt(i->i).toArray();
两者的输出：
[1, 10, 5, 7, 0]
于 2019-01-27T05:16:09.197 回答
0
可以说，你有一个像
int a[] = {0,3,0,4,5,6,0};
然后你可以像这样排序，
for(int i=0;i<a.length;i++){
for(int j=i+1;j<a.length;j++){
if(a[i]==0 && a[j]!=0){
a[i]==a[j];
a[j]=0;
}
}
}
于 2019-06-27T15:21:25.773 回答
0
public void test1(){
int [] arr = {0,1,0,4,0,3,2};
System.out.println("Lenght of array is " + arr.length);
for(int i=0; i < arr.length; i++){
for(int j=0; j < arr.length - i - 1; j++){
if(arr[j] == 0){
int temp = arr[j];
arr[j] = arr[arr.length - i - 1];
arr[arr.length - i - 1] = temp;
}
}
}
for(int x = 0; x < arr.length; x++){
System.out.println(arr[x]);
}
}
于 2019-07-17T08:32:45.317 回答
0
看看这个函数代码：
vector<int> Solution::solve(vector<int> &arr) {
int count = 0;
for (int i = 0; i < arr.size(); i++)
if (arr[i] != 0)
arr[count++] = arr[i];
while (count < arr.size())
arr[count++] = 0;
return arr;
}
于 2020-02-25T19:39:21.063 回答
0
import java.io.*;
import java.util.*;
class Solution {
public static int[] moveZerosToEnd(int[] arr) {
int j = 0;
for(int i = 0; i < arr.length; i++) {
if(arr[i] != 0) {
swap(arr, i, j);
j++;
}
}
return arr;
}
private static void swap(int arr[], int i, int j){
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
public static void main(String[] args) {
int arr[] =new int[] {1, 10, 0, 2, 8, 3, 0, 0, 6, 4, 0, 5, 7, 0 };
System.out.println(Arrays.toString(moveZerosToEnd(arr)));
}
}
于 2020-11-03T19:19:21.963 回答
-1
在 Python 中重新实现：
Pythonic方式：
lst = [ 1, 2, 0, 0, 0, 3, 4, 0, 5, 0 ]
for i, val in enumerate(lst):
if lst[i] == 0:
lst.pop(i)
lst.append(0)
print("{}".format(lst))
@dcow 在 python 中的实现：
lst = [ 1, 2, 0, 0, 0, 3, 4, 0, 5, 0 ]
i = 0 # init the index value
for j in range(len(lst)): # using the length of list as the range
if lst[j] != 0:
if i < j:
lst[i], lst[j] = lst[j], lst[i] # swap the 2 elems.
i += 1
print("{}".format(lst))
于 2014-11-09T21:42:23.147 回答
-1
a = [ 1, 2, 0, 0, 0, 3, 4, 0, 5, 0 ]
count = 0
for i in range(len(a)):
if a[i] != 0:
a[count], a[i] = a[i], a[count]
count += 1
print(a)
#op [1, 2, 3, 4, 5, 0, 0, 0, 0, 0]
于 2019-08-06T15:39:45.447 回答