همه عناصر منفی را به ترتیب با فضای اضافی به ترتیب منتقل کنید  


سطح دشواری ساده
اغلب در یکی از سرمایه خودتان هستید؟ آی بی ام آزمایشگاههای SAP Taxi4Sure Twilio
صف

بیان مسأله  

"تمام عناصر منفی را به ترتیب با فضای اضافی منتقل کنید تا تمام شود" بیان می کند که به شما آرایه ای حاوی اعداد مثبت و منفی هردو داده می شود. دستور مسئله می خواهد تمام عناصر منفی را در آخرین آرایه منتقل کند.

مثال  

arr[] = { 1,2,-3,-5,2,7,-9,-11 }
1, 2, 2, 7, -3, -5, -9, -11
توضیح: تمام مقادیر منفی به آخرین آرایه منتقل شده اند. و آنها نیز در ترتیب اولیه هستند.

الگوریتم برای انتقال همه عناصر منفی به ترتیب با فضای اضافی مجاز  

1. Declare an array same as the size of the original array.
2. Traverse the array and check if any number is greater than or equal to 0,
    1. If true then copy that number from the 0th position of the array we created.
3. Now traverse the array and check if any of the numbers is less than 0.
    1. If true, then copy that value to the array we created from the next position where the positive number ends.
4. Now copy that temporary array we created into the original array and print that array.

توضیح

به ما داده می شود عدد صحیح آرایه ای شامل هر دو عدد منفی و مثبت است. ما خواسته ایم که ترتیب آرایه را به گونه ای تنظیم کنیم که مجبور شویم همه عناصر منفی را به انتهای انتهای آرایه منتقل کنیم. سپس آرایه را برای عناصر مثبت و منفی جداگانه رد و بدل خواهیم کرد. اول ، ما باید عناصر مثبت را در جایی که باید آنها را به سمت چپ بکشیم ، انجام دهیم. و سپس تمام عناصر منفی را به سمت راست تغییر دهید.

همچنین مشاهده کنید
دومین کلمه تکرار شده در یک دنباله

ما باید یک آرایه اضافی با همان اندازه آرایه اصلی ایجاد کنیم. زیرا در این حالت ، ترتیب دلخواه اعداد را ذخیره خواهیم کرد. جمع آوری شاخص متغیر و مقداردهی اولیه آن به صورت 0. این متغیر به ما کمک می کند تا بین عناصر مثبت و منفی تفاوت قائل شویم. اکنون ما یک آرایه ایجاد کردیم. ما اعداد مثبت را از آرایه اصلی به آرایه موقتی قرار خواهیم داد.

ما هنگام تراورس بررسی خواهیم کرد که آیا عناصر آرایه بزرگتر یا مساوی 0 است ، سپس فقط آن عنصر را از موقعیت شروع آرایه موقت در آرایه موقت کپی می کنیم. همچنین ، ما به طور همزمان مقدار شاخص را افزایش می دهیم ، بنابراین از آنجا که آخرین بار عنصر مثبت را کپی کردیم ، از عنصر بعدی که در آن ذخیره می شود ، یک شاخص شاخص داریم ، با کمک این موارد در آخر همه عناصر منفی را تحت فشار قرار خواهیم داد.

حالا ما دوباره به دنبال آرایه می رویم و بررسی می کنیم که آیا هر یک از عناصر صفر است یا نه ، سپس شروع به فشار دادن آن مقدار به داخل آرایه موقت از مقدار شاخصی که ما آن را متوقف کردیم ، می کنیم. سرانجام ، آن آرایه را در آرایه اصلی کپی کنید سپس آن را چاپ کنید یا به سادگی چاپ آرایه موقت را چاپ کنید ، هر دو چیز یکسانی هستند. و ما خروجی مورد نیاز را می گیریم.

همه عناصر منفی را به ترتیب با فضای اضافی به ترتیب منتقل کنید

رمز  

کد C ++ برای انتقال همه عناصر منفی به ترتیب با فضای اضافی مجاز

#include<bits/stdc++.h>
using namespace std;

void segregateElements(int arr[], int n)
{
    int temp[n];

    int j = 0;

    for (int i = 0; i < n ; i++)
        if (arr[i] >= 0 )
            temp[j++] = arr[i];

    if (j == n || j == 0)
        return;

    for (int i = 0 ; i < n ; i++)
        if (arr[i] < 0)
            temp[j++] = arr[i];

    memcpy(arr, temp, sizeof(temp));
}

void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = { 1,2,-3,-5,2,7,-9,-11 };
    int n = sizeof(arr)/sizeof(arr[0]);

    segregateElements(arr, n);
    printArray(arr,n);

    return 0;
}
1 2 2 7 -3 -5 -9 -11

کد جاوا برای انتقال همه عناصر منفی به ترتیب با فضای اضافی مجاز

import java.util.Arrays;

class moveNegativeElement
{
    public static void segregateElements(int arr[], int n)
    {
        int temp[] = new int[n];

        int j = 0;

        for (int i = 0; i < n; i++)
            if (arr[i] >= 0)
                temp[j++] = arr[i];

        if (j == n || j == 0)
            return;

        for (int i = 0; i < n; i++)
            if (arr[i] < 0)
                temp[j++] = arr[i];

        for (int i = 0; i < n; i++)
            arr[i] = temp[i];
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
    public static void main(String arg[])
    {
        int arr[] = { 1,2,-3,-5,2,7,-9,-11 };
        int n = arr.length;

        segregateElements(arr, n);
        printArray(arr,n);

    }
}
1 2 2 7 -3 -5 -9 -11

تحلیل پیچیدگی  

پیچیدگی زمان

بر) جایی که "N" عناصر موجود در آرایه است. ما به سادگی آرایه ای را رد کرده ایم که به دلیل آن به پیچیدگی زمانی خطی دست یافته ایم.

همچنین مشاهده کنید
تقسیم بندی سه طرفه آرایه در محدوده مشخص شده

پیچیدگی فضا

بر) جایی که "N" عناصر موجود در آرایه است. ما یک آرایه اضافی برای استفاده موقتی ایجاد کرده ایم که عناصر را به روش دلخواه ذخیره کرده ایم.