本文概述
给定一个大小为整数的数组n。假设"0"为无效数字, 所有其他均为有效数字。转换数组的方式是, 如果下一个数字是有效数字并且与当前数字相同, 则将其值加倍并将下一个数字替换为0。修改后, 重新排列数组, 使所有0都移到末尾。
例子:
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
资源: 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#
// 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
时间复杂度:O(n)。