算法设计：将第一个元素加倍，然后将零移动到结尾

2021年3月28日16:05:23 发表评论 867 次浏览

本文概述

``````Input : arr[] = {2, 2, 0, 4, 0, 8}
Output : 4 4 8 0 0 0

Input : arr[] = {0, 2, 2, 2, 0, 6, 6, 0, 0, 8}
Output :  4 2 12 8 0 0 0 0 0 0``````

``````1. if n == 1
2.     return
3. for i = 0 to n-2
4.     if (arr[i] != 0) && (arr[i] == arr[i+1])
5.         arr[i] = 2 * arr[i]
6.       arr[i+1] = 0
7.       i++``````

C ++

``````// C++ implementation to rearrange the array
// elements after modification
#include <bits/stdc++.h>

using namespace std;

// function which pushes all zeros to end of
// an array.
void pushZerosToEnd( int arr[], int n)
{
// Count of non-zero elements
int count = 0;

// Traverse the array. If element encountered
// is non-zero, then replace the element at
// index 'count' with this element
for ( int i = 0; i < n; i++)
if (arr[i] != 0)

// here count is incremented
arr[count++] = arr[i];

// Now all non-zero elements have been shifted
// to front and 'count' is set as index of
// first 0. Make all elements 0 from count
// to end.
while (count < n)
arr[count++] = 0;
}

// function to rearrange the array elements
// after modification
void modifyAndRearrangeArr( int arr[], int n)
{
// if 'arr[]' contains a single element
// only
if (n == 1)
return ;

// traverse the array
for ( int i = 0; i < n - 1; i++) {

// if true, perform the required modification
if ((arr[i] != 0) && (arr[i] == arr[i + 1])) {

// double current index value
arr[i] = 2 * arr[i];

// put 0 in the next index
arr[i + 1] = 0;

// increment by 1 so as to move two
// indexes ahead during loop iteration
i++;
}
}

// push all the zeros at the end of 'arr[]'
pushZerosToEnd(arr, n);
}

// function to print the array elements
void printArray( int arr[], int n)
{
for ( int i = 0; i < n; i++)
cout << arr[i] << " " ;
}

// Driver program to test above
int main()
{
int arr[] = { 0, 2, 2, 2, 0, 6, 6, 0, 0, 8 };
int n = sizeof (arr) / sizeof (arr[0]);

cout << "Original array: " ;
printArray(arr, n);

modifyAndRearrangeArr(arr, n);

cout << "\nModified array: " ;
printArray(arr, n);

return 0;
}``````

Java

``````// Java implementation to rearrange the
// array elements after modification
class GFG {

// function which pushes all
// zeros to end of an array.
static void pushZerosToEnd( int arr[], int n)
{
// Count of non-zero elements
int count = 0 ;

// Traverse the array. If element
// encountered is non-zero, then
// replace the element at index
// 'count' with this element
for ( int i = 0 ; i < n; i++)
if (arr[i] != 0 )

// here count is incremented
arr[count++] = arr[i];

// Now all non-zero elements
// have been shifted to front and
// 'count' is set as index of first 0.
// Make all elements 0 from count to end.
while (count < n)
arr[count++] = 0 ;
}

// function to rearrange the array
//  elements after modification
static void modifyAndRearrangeArr( int arr[], int n)
{
// if 'arr[]' contains a single element
// only
if (n == 1 )
return ;

// traverse the array
for ( int i = 0 ; i < n - 1 ; i++) {

// if true, perform the required modification
if ((arr[i] != 0 ) && (arr[i] == arr[i + 1 ]))
{

// double current index value
arr[i] = 2 * arr[i];

// put 0 in the next index
arr[i + 1 ] = 0 ;

// increment by 1 so as to move two
// indexes ahead during loop iteration
i++;
}
}

// push all the zeros at
// the end of 'arr[]'
pushZerosToEnd(arr, n);
}

// function to print the array elements
static void printArray( int arr[], int n)
{
for ( int i = 0 ; i < n; i++)
System.out.print(arr[i] + " " );
System.out.println();
}

// Driver program to test above
public static void main(String[] args)
{
int arr[] = { 0 , 2 , 2 , 2 , 0 , 6 , 6 , 0 , 0 , 8 };
int n = arr.length;

System.out.print( "Original array: " );
printArray(arr, n);

modifyAndRearrangeArr(arr, n);

System.out.print( "Modified array: " );
printArray(arr, n);
}
}

// This code is contributed
// by prerna saini``````

Python3

``````# Python3 implementation to rearrange
# the array elements after modification

# function which pushes all zeros
# to end of an array.
def pushZerosToEnd(arr, n):

# Count of non-zero elements
count = 0

# Traverse the array. If element
# encountered is non-zero, then
# replace the element at index
# 'count' with this element
for i in range ( 0 , n):
if arr[i] ! = 0 :

# here count is incremented
arr[count] = arr[i]
count + = 1

# Now all non-zero elements have been
# shifted to front and 'count' is set
# as index of first 0. Make all
# elements 0 from count to end.
while (count < n):
arr[count] = 0
count + = 1

# function to rearrange the array
# elements after modification
def modifyAndRearrangeArr(ar, n):

# if 'arr[]' contains a single
# element only
if n = = 1 :
return

# traverse the array
for i in range ( 0 , n - 1 ):

# if true, perform the required modification
if (arr[i] ! = 0 ) and (arr[i] = = arr[i + 1 ]):

# double current index value
arr[i] = 2 * arr[i]

# put 0 in the next index
arr[i + 1 ] = 0

# increment by 1 so as to move two
# indexes ahead during loop iteration
i + = 1

# push all the zeros at the end of 'arr[]'
pushZerosToEnd(arr, n)

# function to print the array elements
def printArray(arr, n):

for i in range ( 0 , n):
print (arr[i], end = " " )

# Driver program to test above
arr = [ 0 , 2 , 2 , 2 , 0 , 6 , 6 , 0 , 0 , 8 ]
n = len (arr)

print ( "Original array:" , end = " " )
printArray(arr, n)

modifyAndRearrangeArr(arr, n)

print ( "\nModified array:" , end = " " )
printArray(arr, n)

# This code is contributed by Smitha Dinesh Semwal``````

C#

``````// C# implementation to rearrange the
// array elements after modification
using System;

class GFG {

// function which pushes all
// zeros to end of an array.
static void pushZerosToEnd( int [] arr, int n)
{
// Count of non-zero elements
int count = 0;

// Traverse the array. If element
// encountered is non-zero, then
// replace the element at index
// 'count' with this element
for ( int i = 0; i < n; i++)
if (arr[i] != 0)

// here count is incremented
arr[count++] = arr[i];

// Now all non-zero elements
// have been shifted to front and
// 'count' is set as index of first 0.
// Make all elements 0 from count to end.
while (count < n)
arr[count++] = 0;
}

// function to rearrange the array
// elements after modification
static void modifyAndRearrangeArr( int [] arr, int n)
{
// if 'arr[]' contains a single element
// only
if (n == 1)
return ;

// traverse the array
for ( int i = 0; i < n - 1; i++) {

// if true, perform the required modification
if ((arr[i] != 0) && (arr[i] == arr[i + 1])) {

// double current index value
arr[i] = 2 * arr[i];

// put 0 in the next index
arr[i + 1] = 0;

// increment by 1 so as to move two
// indexes ahead during loop iteration
i++;
}
}

// push all the zeros at
// the end of 'arr[]'
pushZerosToEnd(arr, n);
}

// function to print the array elements
static void printArray( int [] arr, int n)
{
for ( int i = 0; i < n; i++)
Console.Write(arr[i] + " " );
Console.WriteLine();
}

// Driver program to test above
public static void Main()
{
int [] arr = { 0, 2, 2, 2, 0, 6, 6, 0, 0, 8 };
int n = arr.Length;

Console.Write( "Original array: " );
printArray(arr, n);

modifyAndRearrangeArr(arr, n);

Console.Write( "Modified array: " );
printArray(arr, n);
}
}

// This code is contributed by Sam007``````

``````Original array: 0 2 2 2 0 6 6 0 0 8
Modified array: 4 2 12 8 0 0 0 0 0 0``````