算法设计（将第一个元素加倍，然后将零移动到结尾） _数据结构

本文概述

C ++
Java
Python3
C#

给定一个大小为整数的数组n。假设"0"为无效数字, 所有其他均为有效数字。转换数组的方式是, 如果下一个数字是有效数字并且与当前数字相同, 则将其值加倍并将下一个数字替换为0。修改后, 重新排列数组, 使所有0都移到末尾。
例子：

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

资源： Microsoft IDC面试体验|S150。
方法：首先按照上述说明修改数组, 即, 如果下一个有效数字与当前数字相同, 则将其值加倍, 然后将下一个数字替换为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# 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

输出如下：