Барлық нөлдерді берілген массивтің соңына жылжытыңыз


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon алма Bloomberg ByteDance Capital One Cisco Dell еВау Facebook Голдман Сакс Google IBM LinkedIn Microsoft Нутаниx Oracle PayPal Paytm Qualcomm Samsung SAP зертханалары ServiceNow Splunk Tesla қиятын Walmart зертханалары Yahoo Яндекс Zillow
Array Екі нұсқағыш

Проблемалық мәлімдеме

Аталған массив жиымда бар барлық нөлдерді жиымның соңына дейін жылжытыңыз. Нөлдердің барлық санын массивтің соңына кірістіру әдісі әрқашан бар.

мысал

енгізу

9

9 17 0 14 0 0 23 19 4

шығыс

9 17 4 14 19 23 0 0 0

Барлық нөлдерді берілген массивтің соңына жылжыту алгоритмі

Қадам 1: Берілген жиымда айнымалылар сияқты екі көрсеткішті алыңыз. Сол жақ = 0, оң = N -1 инициализациясы (N - массивтің өлшемі).
а. Left - бірінші элементтегі сол жақ көрсеткіштің айнымалысы.
б. Right - соңғы элементтегі оң көрсеткіштің айнымалысы.

Қадам 2: Солдан солға қарай жүріңіз, егер нөл нөлге дейін, ал нөлге дейін аяғына қарай табылса, оларды жай ғана ауыстырыңыз.
а. Солдан, егер элемент нөлге тең болмаса, алға жылжытыңыз.
б. Егер нөл табылса, онда артқы жағынан нөлдік емес элементтерге қарай оң көрсеткіштен өтіңіз, егер табылған нөл жүрісті жалғастыра берсе.
в. Егер нөлге тең емес болса, сол жақ меңзермен ауыстырыңыз.
г. Соңында, барлық нөлдер массивтің соңына дейін итеріледі.

Қадам 3: Нөлдердің соңына дейін итерілуін тексеру үшін массивті басып өткеннен кейін басып шығарыңыз.

Барлық нөлдерді берілген массивтің соңына жылжыту туралы түсініктеме

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

1-қадам: 0-ден солға және n-1-ден оңға.

2-қадам: Біз 0 кездескенше сол жақ көрсеткішті үлкейтіңіз. Содан кейін сол = 2. Енді біз [солға], [оңға] ауыстырамыз және сол жақ көрсеткішті үлкейтіп, массивтегі нөлдік емес элементтерді білдіретін оң жақ көрсеткішті кішірейтеміз.

 3-қадам: Әрі қарай сол жақ көрсеткішті тағы бір нөлге жеткенше көбейтеміз, содан кейін солға = 4. Енді біз [солға], [оңға] ауыстырамыз, ал сол жақ көрсеткішті үлкейтеміз және массивтегі нөлдік емес элементтерді білдіретін оң жақ көрсеткішті кішірейтеміз.

4-қадам: Мұнда біз нөлге тап болдық. Сонымен, біз оны нұсқағыштың дұрыс орналасқан элементімен ауыстырамыз.

5-қадам: Енді кез келген нөлге жеткенше сол жақ меңзерді көбейтіңіз. Енді біз өсімді және сол жақта> оң жақта ұстаймыз, осылайша циклды тоқтатамыз.

Демек, [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) өйткені мұнда біз бірнеше айнымалыларды ғана қолданамыз, бұл бізді үнемі кеңістіктің күрделілігіне әкеледі.

Әдебиеттер тізімі