انقل كل الأصفار إلى نهاية المصفوفة المعطاة


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل بلومبرغ ByteDance عاصمة واحدة سيسكو ديل يباي Facebook جولدمان ساكس جوجل IBM لينكد إن: Microsoft Nutanix أوراكل Paypal Paytm كوالكوم سامسونج مختبرات SAP الخدمة الآن Splunk تسلا اوبر مختبرات وول مارت ياهو ياندكس Zillow
مجموعة اثنين من المؤشرات

المشكلة بيان

في إعطاء مجموعة انقل جميع الأصفار الموجودة في المصفوفة إلى نهاية المصفوفة. توجد هنا دائمًا طريقة لإدراج كل عدد الأصفار في نهاية المصفوفة.

مثال

إدخال

9

شنومكس شنومكس شنومكس شنومكس شنومكس شنومكس شنومكس شنومكس شنومكس

الناتج

شنومكس شنومكس شنومكس شنومكس شنومكس شنومكس شنومكس شنومكس شنومكس

خوارزمية لنقل كل الأصفار إلى نهاية المصفوفة المعطاة

خطوة 1: في المصفوفة المحددة ، خذ مؤشرين مثل المتغيرات. التهيئة يسار = 0 ، يمين = N -1 (N هو حجم المصفوفة).
أ. Left هو متغير المؤشر الأيسر عند العنصر الأول.
ب. Right هو متغير المؤشر الأيمن في العنصر الأخير.

خطوة 2: قم بالانتقال من اليسار بحيث إذا تم العثور على صفر باتجاه البداية وغير الصفر باتجاه النهاية ، فقم ببساطة بتبديلهما.
أ. من اليسار ، إذا كان العنصر غير صفري ، فانتقل إلى الأمام.
ب. إذا تم العثور على الصفر ، فانتقل من الخلف باتجاه العناصر غير الصفرية من المؤشر الأيمن ، إذا تم العثور على الصفر ، فاستمر في العبور.
ج. إذا لم يتم العثور على الصفر ، فقم بالتبديل بالمؤشر الأيسر.
د. أخيرًا ، يتم دفع جميع الأصفار إلى نهاية المصفوفة.

خطوة 3: اطبع المصفوفة بعد اجتيازها للتحقق من دفع الأصفار إلى النهاية.

شرح لنقل كل الأصفار إلى نهاية المصفوفة المعطاة

أ [] = {9 ، 17 ، 0 ، 14 ، 0 ، 0 ، 23 ، 19 ، 4}

الخطوة الأولى: يسار عند 0 ويمين عند n-1.

الخطوة الثانية: قم بزيادة المؤشر الأيسر حتى نواجه 0. ثم اليسار = 2. الآن نقوم بتبديل [يسار] و [يمين] وزيادة المؤشر الأيسر وتقليل المؤشر الأيمن الذي يشير إلى العناصر غير الصفرية في المصفوفة.

 الخطوة الثالثة: بعد ذلك نزيد المؤشر الأيسر حتى نواجه صفرًا آخر ، ثم اليسار = 4. الآن نقوم بتبديل [يسار] و [يمين] وزيادة المؤشر الأيسر وتقليل المؤشر الأيمن الذي يشير إلى العناصر غير الصفرية في المصفوفة.

الخطوة الرابعة: هنا نواجه بالفعل صفرًا. لذلك ، نقوم بتبديله بالعنصر الموجود في موضع المؤشر الأيمن.

الخطوة الرابعة: الآن ، قم بزيادة المؤشر الأيسر حتى نواجه أي صفر. الآن نحافظ على الزيادة واليسار> اليمين حتى ننهي الحلقة.

لذلك ، بالنسبة للمدخلات المعطاة [9,17,0,14,0,0,23,19,4،9,17,4,14,19,23,0,0,0،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX] يكون ناتجنا [XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX].

تطبيق

برنامج 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;
}

برنامج جافا

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 هو حجم المصفوفة. هنا نستخدم فقط مؤشرين ونستمر في تقليل الطول بينهما. لذلك ، يقودنا ذلك إلى التعقيد الزمني الخطي.

تعقيد الفضاء

يا (1) لأننا هنا نستخدم فقط بعض المتغيرات التي تقودنا إلى تعقيد مكاني ثابت.

مراجع