將所有零移動到給定數組的末尾  


難度級別 容易獎學金
經常問 土磚 亞馬遜 蘋果 彭博社 ByteDance 第一資本 思科 戴爾 易趣 Facebook 高盛 谷歌 IBM LinkedIn Microsoft微軟 Nutanix 神諭 貝寶 Paytm 高通公司 Samsung SAP實驗室 的ServiceNow Splunk的 特斯拉 尤伯杯 沃爾瑪實驗室 雅虎 Yandex的 Zillow的
排列 兩個指針

問題陳述  

在給定的 排列 將數組中存在的所有零移動到數組的末尾。 這裡總是存在一種將所有零數字插入到數組末尾的方法。

例  

輸入

9

9 17 0 14 0 0 23 19 4

產量

9 17 4 14 19 23 0 0 0

將所有零移動到給定數組末尾的算法  

STEP 1: 在給定的數組中,採用兩個指針,如變量。 初始化left = 0,right = N -1(N是數組的大小)。
一種。 Left是第一個元素的左指針變量。
b。 右是最後一個元素的右指針變量。

STEP 2: 從左側開始遍歷,這樣,如果在開始處發現零,而在結束處發現非零,則只需交換它們。
一種。 從左開始,如果元素為非零,則繼續前進。
b。 如果找到零,則從右指針向後遍歷到非零元素,如果找到零則繼續遍歷。
C。 如果找到非零值,則與左指針交換。
d。 最後,所有零都被推到數組的末尾。

STEP 3: 遍歷後打印數組以檢查是否將零推到末尾。

也可以看看
不使用多餘空間將2n個整數隨機排列為a1-b1-a2-b2-a3-b3-.bn

將所有零移動到給定數組的末尾的說明  

a [] = {9,17,0,14,0,0,23,19,4}

第一步: 左為0,右為n-1。

第二步: 遞增左指針,直到遇到0。然後left = 2。 現在,我們交換a [left],a [right],並增加左指針,並減少表示數組中非零元素的右指針。

 第三步: 接下來,我們增加左指針,直到遇到另一個零,然後左= 4。 現在,我們交換a [left],a [right],並增加左指針,並減少表示數組中非零元素的右指針。

第四步: 在這裡,我們已經遇到了零。 因此,我們將其與位於正確指針位置的元素交換。

第四步: 現在,增加左指針,直到遇到零為止。 現在,我們保持增量,而我們的left> right則終止循環。

因此,對於給定的輸入[9,17,0,14,0,0,23,19,4],我們的輸出為[9,17,4,14,19,23,0,0,0]。

履行  

C ++程序

#include <bits/stdc++.h>
using namespace std;
int main()
{
  
  int N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  int left = 0 , right = N-1; // take two pointer like variables for traversal
  
  while(left < right)
  {
    if(arr[left] != 0) // if element not zero then move ahead
      left ++;
    if(arr[right] == 0) // if ending elments are zero then come backwards towards non zero elements
      right --;
      
    if(arr[left] == 0 and arr[right] != 0) // if a zero is found towards start and non zero towards end then simply swap it
        {  
        swap(arr[left++],arr[right--]);
        }
  } 
  
  for(int i = 0; i < N;i++)
    cout <<arr[i]<<" ";
  return 0;
}

Java程序

import static java.lang.Math.sqrt;
import java.util.Arrays;
import java.util.Scanner;

class sum
{
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        }
        int left = 0 , right = n-1; // take two pointer like variables for traversal
        while(left < right)
        {
          if(arr[left] != 0) // if element not zero then move ahead
            left ++;
          if(arr[right] == 0) // if ending elments are zero then come backwards towards non zero elements
            right --;
          if(arr[left] == 0 && arr[right] != 0) // if a zero is found towards start and non zero towards end then simply swap it
              {  
              arr[left]=arr[left]+arr[right]-(arr[right]=arr[left]);
              left++;
              right--;
              }
        } 

        for(int i=0;i<n;i++)
          System.out.print(arr[i]+" ");
    }
}
9
9 17 0 14 0 0 23 19 4
9 17 4 14 19 23 0 0 0

將所有零移動到給定數組末尾的複雜度分析  

時間複雜度

也可以看看
合併兩個平衡的二叉搜索樹

O(N) 其中n是數組的大小。 在這裡,我們只使用兩指針,並保持縮短它們之間的長度。 因此,這導致我們線性時間複雜度。

空間複雜度

O(1) 因為在這裡我們僅使用一些變量,這導致我們不斷的空間複雜性。

參考