有一个固定长度的整数数组
arr，每次出现零都重复，将剩余元素右移。超出原始数组长度的元素不会被写入
我们必须修改输入数组，而不必创建新数组。
所以我创建了它，但它复制了数组末尾的零，而不是之前的零。有人能帮我吗？
public static void addPos() {
int arr[] = { 1, 2, 0, 3, 0, 5, 0, 7, 8 };
int result[] = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
int loc = i;
for (int j = 0; j < loc; j++) {
result[j] = arr[j];
result[loc] = 0;
}
for (int j = loc + 1; j < arr.length; j++) {
result[j] = arr[j - 1];
}
}
}
for (int k = 0; k < arr.length; k++)
System.out.println(result[k]);
}
输出
1
2
0
3
0
5
0
0
7
Expected output:
1
2
0
0
3
0
0
5
0
循环的每一次迭代都会覆盖上一次迭代的结果，因此最终结果只显示上一次重复的结果，重复了上一次0。
解决这一问题的一种方法是通过向后迭代"；"从右到左"；。它简化了很多事情。您可以去掉辅助result数组。基本思想是，在数组中倒退，每次找到0时，都会通过将数组重写到0的右边来复制它。
public static void addPos() {
int arr[] = {1, 2, 0, 3, 0, 5, 0, 7, 8};
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] == 0) {
// duplicate it!
for (int j = arr.length - 1; j > i; j--) {
arr[j] = arr[j-1];
}
}
}
for (int k = 0; k < arr.length; k++) {
System.out.println(arr[k]);
}
}
for循环不断覆盖结果数组中的值，因此结果只显示最后一次重复。您根本不应该使用结果数组。保持在原始数组本身中传递值。
您可以参考以下代码。
for(int i=0;i<arr.length-1;i++){
if(arr[i]==0){
for(int j=arr.length-1;j>i;j--){
arr[j]=arr[j-1];
}
i++;
}
}
public void duplicateZeros(int[] arr)
{int i=0；
while(i<arr.length)
{
if(arr[i]==0)
{
int j=arr.length-1;
while(j != i)
{
arr[j]=arr[j-1];
j--;
}
i=i+2;
}
else
{
i=i+1;
}
}
}
不使用任何其他数组。
class Solution {
public void duplicateZeros(int[] arr) {
for(int i=0;i<arr.length;i++){
if(arr[i]==0){
for(int j=arr.length-1;j>i;j--){
arr[j]=arr[j-1];
}
i=i+1;
}
}
}
}
所以有这样一个：
int[] arr = { 1, 2, 0, 3, 0, 5, 0, 7, 8 };
public static void duplicateZeros(int[] arr) {
并且应该得到
{ 1, 2, 0, 3, 0, 5, 0, 7, 8 }
v___
{ 1, 2, 0, 0, 3, 0, 5, 0, 7 }
v___
{ 1, 2, 0, 0, 3, 0, 0, 5, 0 }
这看起来像：
for (int i = 1; i < n; ++i) {
if (arr[i - 1] == 0) {
insert at i a 0;
}
}
insert at i a 0:
// First move the remaining to the right: i .. n-2
...
// Then fill in the zero
arr[i] = 0;
任何感兴趣的人的Python解决方案从这里改编
如果不将指针在列表上迭代的操作和插入操作分开，那么解决方案就不是微不足道的了。写一个for循环来无限添加0是很容易的。
def duplicateZeros(arr):
# define the incrementor
i = 0
# loop through all dynamic elements
while i < len(arr)-1:
# if the character is a zero
if arr[i]==0:
# remove the last item from the array
arr.pop()
# insert a zero in front of current element
arr.insert(i+1, 0)
# move one place forward
i += 1
# increment to the next character
i += 1
解决方案1:从头到尾循环。如果找到零，则从下一个索引中移动元素，并将下一个填充为零，然后跳过下一个。
public static void duplicateZeros(int[] arr) {
System.out.println("BEGIN duplicateZeros:" + Arrays.toString(arr));
for(int i=0; i<arr.length-1; ++i) {
if (arr[i] == 0) {
move(arr, i);
++i;
}
}
System.out.println("END duplicateZeros:" + Arrays.toString(arr) +"n");
}
private static void move(int[] arr, int index) {
// move to the right from index+1
for(int i=arr.length-1; i>index; i--) {
arr[i] = arr[i-1];
}
// fill 0 at index
arr[index] = 0 ;
}
解决方案2:从头到尾循环。如果找到零，则从下一个索引中移动元素，并将当前索引填充为零。
public static void duplicateZeros(int[] arr) {
System.out.println("BEGIN duplicateZeros:" + Arrays.toString(arr));
for(int i=arr.length-1; i>=0; i--) {
if (arr[i] == 0) {
move(arr, i);
}
}
System.out.println("END duplicateZeros:" + Arrays.toString(arr) +"n");
}
private static void move(int[] arr, int index) {
// move to the right from index+1
for(int i=arr.length-1; i>index; i--) {
arr[i] = arr[i-1];
}
// fill 0 at index
arr[index] = 0 ;
}
class Solution:
def duplicateZeros(self, arr: List[int]) -> None:
"""
Do not return anything, modify arr in-place instead.
"""
if len(arr)==0:
return arr
index = 0
while index < len(arr):
print(index,end=" ")
if arr[index]==0:
arr.insert(index+1,0)
arr.pop()
index+=1
index+=1