Bütün Sıfırları Verilən Arrayın Sonuna aparın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Çiy kərpic Amazon alma Bloomberg ByteDance Capital One Cisco Vadi eBay Facebook Goldman Sachs google IBM LinkedIn microsoft Nutanix Kahin PayPal Paytm Qualcomm Samsung SAP Laboratoriyaları XidmətNow Boşalmaq Tesla Über Walmart Laboratoriyaları Yahoo Yandex Zillow
Geyim İki işarəBaxılıb 507

Problem bəyanat

verilmiş In array massivdə olan bütün sıfırları massivin sonuna aparın. Burada bütün sıfır sayını massivin sonuna əlavə etmək üçün həmişə bir yol var.

misal

Input

9

9 17 0 14 0 0 23 19 4

Buraxılış

9 17 4 14 19 23 0 0 0

Bütün Sıfırları Verilən Arrayın Sonuna Daşıma Alqoritmi

1 Adım: Verilən massivdə dəyişənlər kimi iki göstərici götürün. Soldan başlanğıc = 0, sağ = N -1 (N sıra ölçüsüdür).
a. Sol ilk elementdəki sol göstərici dəyişənidir.
b. Sağ, son elementdəki sağ göstərici dəyişənidir.

2 Adım: Soldan keçin ki, başlanğıcda sıfır, sona doğru sıfır tapılsın, sadəcə onları dəyişdirin.
a. Soldan, element sıfır deyilsə irəliləyin.
b. Əgər sıfır tapılarsa, arxadan sağ göstəricidən sıfır olmayan elementlərə doğru keçin, əgər tapılan sıfır keçməyə davam edirsə.
c. Sıfır deyilsə, sol göstərici ilə dəyişdirin.
d. Nəhayət, bütün sıfırlar massivin sonuna itələdilər.

3 Adım: Sıfırların sona qədər itələdiyini yoxlamaq üçün keçiddən sonra serialı çap edin.

Bütün Sıfırları Verilən Arrayın Sonuna Daşımağın İzahı

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

1-ci addım: 0-da və n-1-də sağda.

2-ci addım: 0 ilə qarşılaşana qədər sol göstəricini artırın. Sonra sol = 2. İndi a [sol], a [sağ] dəyişdiririk və sol göstəricini artırırıq və massivdəki sıfır olmayan elementləri ifadə edən sağ göstəricini azaldırıq.

 3-cü addım: Sonra başqa bir sıfırla qarşılaşana qədər sol göstəricini artırırıq, sonra sola = 4. İndi a [sol], a [sağ] dəyişdiririk və sol göstəricini artırırıq və massivdəki sıfır olmayan elementləri ifadə edən sağ göstəricini azaldırıq.

4-cü addım: Burada artıq sıfırla qarşılaşırıq. Beləliklə, onu doğru göstərici mövqeyində olan elementlə dəyişdiririk.

5-cü addım: İndi hər hansı bir sıfırla qarşılaşana qədər sol göstəricini artırın. İndi artımı və solumuzu> sağımızı davam etdiririk, beləliklə döngəni sonlandırırıq.

Bu səbəbdən verilmiş giriş üçün [9,17,0,14,0,0,23,19,4] bizim məhsulumuz [9,17,4,14,19,23,0,0,0].

Həyata keçirilməsi

C ++ Proqramı

#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 Proqramı

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

Bütün Sıfırları Verilən Arrayın Sonuna Keçirmək üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O (n) burada n massivin ölçüsüdür. Burada yalnız iki göstəricidən istifadə edirik və aralarındakı uzunluğu azaltmağa davam edirik. Beləliklə, bizi xətti zaman mürəkkəbliyinə aparır.

Kosmik Mürəkkəblik

O (1) çünki burada bizi daimi kosmik mürəkkəbliyə aparan yalnız bir neçə dəyişəndən istifadə edirik.

References

Translate »