Տեսակավորել զանգվածը ըստ Parity II Leetcode լուծման


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon
Դասավորություն դասավորում

Խնդրի հայտարարություն

Խնդիրի մեջ »Տեսակավորել զանգվածը ըստ Հավասարություն II », - մեզ տրվում է հավասարության զանգված, որտեղ բոլոր տարրերը դրական ամբողջ թվեր են: Rayանգվածը պարունակում է զույգ քանակի տարրեր: Rayանգվածը պարունակում է հավասար թվով զույգ և կենտ տարրեր:

Մեր խնդիրն է զանգվածի տարրերը վերադասավորել այնպես, որ հավասարությունը [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]: Այս զանգվածից որևէ մեկը ճիշտ պատասխան է:

Sանգվածի տեսակավորման մոտեցում ըստ Parity II Leetcode լուծույթի

Այս խնդրի առաջին և հիմնական մոտեցումը նոր զանգված ստեղծելն է, այնուհետև անցնել հին զանգվածը: Երբ մենք հանդիպում ենք զույգի տարրի, ապա այն դնում ենք նոր զանգվածի զույգ դիրքի, իսկ երբ կենտ տարր ենք ունենում, ապա այն դնում ենք նոր զանգվածի կենտ դիրքում: Այս մոտեցումը լրացուցիչ տարածք է օգտագործում, և մենք կարող ենք բարելավել մեր տրամաբանությունը ՝ օգտագործելով տեղում վերադասավորումը:

Տեսակավորել զանգվածը ըստ Parity 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 կոդ ՝ ըստ տեսակավորման զանգվածի ըստ պարիտետի 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 լուծույթի

Timeամանակի բարդությունը

Վերոնշյալ ծածկագրի ժամանակի բարդությունն է O (n) քանի որ մենք մեկ անգամ ենք անցնում հավասարության զանգվածը: Այստեղ n- ը հավասարության զանգվածի երկարությունն է:

Տիեզերական բարդություն

Վերոնշյալ ծածկագրի տիեզերական բարդությունն է Ո (1) քանի որ մենք պատասխանը պահելու համար օգտագործում ենք միայն փոփոխական:

Սայլակ