اعداد زوج و فرد را تفکیک کنید


سطح دشواری ساده
اغلب در همبستگی لینک MakeMyTrip Paytm با
صف مرتب سازی

بیان مسأله

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

مثال

arr[]={ 2,4,5,1,7,8,9,7}
2 4 8 1 7 5 9 7

توضیح: همه عناصر زوج قبل از عناصر فرد قرار می گیرند Thay نیز همان ترتیب را در ورودی داده شده دنبال می کنند.

الگوریتم برای تفکیک اعداد زوج و فرد

1. Set i = -1, j = 0.
2. While j is not equal to n(where n is the length of the array),
    1. Check if arr[j] is even or odd if it is even
        1. Do i++, and swap the values of arr[i] and arr[j] respectively.
    2. Increase the value of j by 1.
3. Print the array.

توضیح

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

سپس ما با گرفتن دو مقدار شاخص برای یک آرایه ، آرایه را پیمایش می کنیم. یکی برای پیمایش منظم و دیگری برای نمایه سازی اعداد زوج است. ما آرایه را با مقدار j رد می کنیم. و بررسی کنید که آیا هر یک از اعداد زوج است اگر arr [j] زوج باشد. سپس ما آن را با arr [i] عوض خواهیم کرد. ما فقط وقتی مقدار آرایه [j] یکنواخت است ، i را افزایش می دهیم. بنابراین حتی اگر اعداد زوج را پیدا نکنیم ، مقدار j را افزایش خواهیم داد. و سپس اگر عدد زوج را پیدا کنیم. سپس arr [j] را با arr [i] که قرار بود یک عدد عجیب باشد ، مبادله خواهیم کرد.

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

اعداد زوج و فرد را تفکیک کنید

رمز

کد ++ C برای تفکیک اعداد زوج و فرد

#include<iostream>

using namespace std;

void getArrangedEvenOdd(int arr[], int n)
{

    int i = -1, j = 0;
    while (j != n)
    {
        if (arr[j] % 2 == 0)
        {
            i++;
            swap(arr[i], arr[j]);
        }
        j++;
    }
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main()
{
    int arr[] = { 2,4,5,1,7,8,9,7};
    int n = sizeof(arr) / sizeof(int);
    getArrangedEvenOdd(arr, n);
    return 0;
}
2 4 8 1 7 5 9 7

کد جاوا را برای تفکیک اعداد زوج و فرد قرار دهید

public class rearrangeEvenOdd
{
    public static void getArrangedEvenOdd( int arr[], int n)
    {

        int i = -1, j = 0;
        while (j != n)
        {
            if (arr[j] % 2 == 0)
            {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
            j++;
        }
        for (int k = 0; k < n; k++)
            System.out.print(arr[k] + " ");
    }
    public static void main(String args[])
    {
        int arr[] = { 2,4,5,1,7,8,9,7};
        int n = arr.length;
        getArrangedEvenOdd (arr, n);
    }
}
2 4 8 1 7 5 9 7

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

پیچیدگی زمان

O (N) جایی که "n" تعداد عناصر آرایه است. در اینجا ما آرایه را رد کرده ایم تا زمانی که شاخص j برابر N نباشد. این بدان معناست که ما یک بار آرایه را رد کردیم. و بنابراین پیچیدگی زمانی خطی.

پیچیدگی فضا

O (1) زیرا فضای اضافی مورد نیاز نیست. الگوریتم خود فقط فضای ثابت را می گیرد اما برنامه به طور کلی فضای خطی را اشغال می کند.