مرتب سازی آرایه براساس Parity II Leetcode Solution


سطح دشواری ساده
اغلب در آمازون
صف مرتب سازی

بیان مسأله

در مسئله ”مرتب سازی بر اساس آرایه برابری II ، "به ما یک آرایه برابری داده می شود که در آن تمام عناصر عدد صحیح مثبت هستند. آرایه شامل تعداد عناصر زوج است. آرایه شامل تعداد مساوی عناصر زوج و فرد است.

وظیفه ما این است که عناصر آرایه را به گونه ای تنظیم کنیم که برابری [i] حاوی یک عنصر زوج باشد در حالی که حتی در غیر این صورت برابری [i] باید حاوی یک عنصر فرد باشد و سپس آرایه جدید را برگرداند.

مثال

parity=[1,2,3,4]
[2,1,4,3]

شرح:  تمام آرایه های ممکن که شرایط را برآورده می کند عبارتند از: [2,1,4,3،2,3,4,1،4,1,2,3،4,3,2,1] ، [XNUMX،XNUMX،XNUMX،XNUMX] ، [XNUMX،XNUMX،XNUMX،XNUMX] ، [XNUMX،XNUMX،XNUMX،XNUMX]. پاسخ هر یک از این آرایه ها درست است.

رویکرد برای مرتب سازی مرتب سازی بر اساس راه حل کد کد Parity II

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

مرتب سازی آرایه براساس Parity II Leetcode Solution

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

  1. متغیر i را با 0 و j را با 1 مقداردهی اولیه کنید. در اینجا من فقط موقعیت زوج را طی می کنیم بنابراین هر بار مقدار آن را 2 افزایش می دهیم و j فقط موقعیت فرد را طی می کند بنابراین مقدار آن را هر بار 2 افزایش می دهیم.
  2. اگر برابری [i] فرد باشد ، aj را پیدا خواهیم کرد که برابری آن [j] برابر باشد و سپس عناصر را در i و j عوض خواهیم کرد.
  3. این مراحل را انجام می دهیم تا زمانی که مقدار i از طول آرایه parity کوچکتر باشد.
  4. آرایه برابری را برگردانید.

پیاده سازی

کد C ++ برای مرتب سازی بر اساس آرایه II

#include <bits/stdc++.h> 
using namespace std; 
    vector<int> sortArrayByParityII(vector<int>& A) {
        int n =A.size();
        int j=1;
         for (int i = 0; i < n; i += 2)
            if (A[i] % 2 == 1) {
                while (A[j] % 2 == 1)
                    j += 2;
                swap(A[i],A[j]); 
            }

        return A;
    }
int main() 
{ 
 vector<int> arr = {1,2,3,4}; 
  vector<int>ans=sortArrayByParityII(arr); 
 for(int i=0;i<arr.size();i++)
 cout<<ans[i]<<" ";
 cout<<endl;
 return 0;
}
[2,1,4,3]

کد جاوا برای مرتب سازی بر اساس آرایه II

import java.util.Arrays; 
public class Tutorialcup {
    public static int[] sortArrayByParityII(int[] A) {
        int n =A.length;
        int j=1;
         for (int i = 0; i < n; i += 2)
            if (A[i] % 2 == 1) {
                while (A[j] % 2 == 1)
                    j += 2;
               swap(A, i, j);
                }

        return A;
    }
     private static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
  public static void main(String[] args) {
        int [] arr = {1,2,3,4}; 
        int[]ans=sortArrayByParityII(arr); 
        System.out.println(Arrays.toString(ans));
  }
}
[2,1,4,3]

تجزیه و تحلیل پیچیدگی آرایه مرتب سازی توسط Parity II Leetcode Solution

پیچیدگی زمانی

پیچیدگی زمانی کد فوق است O (N) زیرا ما فقط یک بار آرایه برابری را رد می کنیم. در اینجا n طول آرایه برابری است.

پیچیدگی فضا

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

منابع