ترتيب الصفيف حسب حل تماثل II Leetcode


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون
مجموعة فرز

بيان المشكلة

في المشكلة "فرز صفيف حسب مساواة II ، "حصلنا على مصفوفة تكافؤ حيث تكون جميع العناصر أعدادًا صحيحة موجبة. تحتوي المصفوفة على عدد زوجي من العناصر. تحتوي المصفوفة على عدد متساوٍ من العناصر الفردية والزوجية.

تتمثل مهمتنا في إعادة ترتيب عناصر المصفوفة بطريقة تجعل التكافؤ [i] يحتوي على عنصر زوجي عندما تكون 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 Leetcode Solution

النهج الأول والأساسي لهذه المشكلة هو إنشاء مصفوفة جديدة ثم اجتياز المصفوفة القديمة. عندما نواجه عنصرًا زوجيًا ، نضعه في الموضع الزوجي للمصفوفة الجديدة وعندما نواجه عنصرًا فرديًا ، نضعه في الموضع الفردي للمصفوفة الجديدة. يستخدم هذا النهج مساحة إضافية ويمكننا تحسين منطقنا باستخدام إعادة الترتيب في المكان.

ترتيب الصفيف حسب حل تماثل II Leetcode

الفكرة هي أنه إذا وضعنا جميع العناصر الزوجية في موضع زوجي ، فستكون العناصر الفردية تلقائيًا في موضع فردي. لذلك نحتاج فقط إلى التركيز على كيفية وضع العناصر المتساوية في مواضع متساوية. سنتبع الخطوات التالية:

  1. قم بتهيئة المتغير i بـ 0 و j بـ 1. هنا سوف أسافر فقط في الموضع الزوجي لذا سنزيد قيمته بمقدار 2 في كل مرة وسينتقل j إلى موضع فردي فقط لذلك سنزيد قيمته بمقدار 2 في كل مرة.
  2. إذا كان التكافؤ [i] غريبًا ، فسنجد aj الذي يكون التكافؤ [j] فيه زوجيًا ثم سنبادل العناصر عند i و j.
  3. سنفعل هذه الخطوات حتى تصبح قيمة i أصغر من طول مصفوفة التكافؤ.
  4. أعد مصفوفة التكافؤ.

تطبيق

كود C ++ لـ Sort Array By Parity 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]

كود Java لـ Sort Array By Parity 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

تعقيد الوقت

التعقيد الزمني للشفرة أعلاه O (ن) لأننا نجتاز مصفوفة التكافؤ مرة واحدة فقط. هنا n هو طول مصفوفة التكافؤ.

تعقيد الفضاء

تعقيد الفضاء من الكود أعلاه يا (1) لأننا نستخدم متغيرًا فقط لتخزين الإجابة.

المراجع