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

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

本文概述

给定一个大小为整数的数组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)。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: