Сортирај низа според паритет II решение за лет код


Ниво на тешкотија Лесно
Често прашувано во Амазон
Низа Сортирање

Проблем изјава

Во проблемот ”Подреди по низа според Паритет 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]. Кој и да е од овие низи е точен одговор.

Пристап за подредување на низата според решение на лек-код II со паритет

Првиот и основен пристап кон овој проблем е да се создаде нова низа и потоа да се помине низ старата низа. Кога ќе наидеме на парен елемент, тогаш ставете го во парна позиција на новата низа и кога ќе се сретнеме со непарен елемент, тогаш ставете го во непарна позиција на новата низа. Овој пристап користи дополнителен простор и можеме да ја подобриме нашата логика со користење на преуредување на место.

Сортирај низа според паритет II решение за лет код

Идејата е ако ги ставиме сите парни елементи во парна позиција, тогаш непарните елементи ќе бидат автоматски во непарна позиција. Значи, треба да се фокусираме само на тоа како да ги поставиме рамномерните елементи во рамномерна положба. Ние ќе ги следиме овие чекори:

  1. Иницијализирај ја променливата i со 0 и j со 1. Овде јас ќе патувам само парна позиција, така што ќе ја зголемуваме нејзината вредност за 2 секој пат и j ќе патува само непарна позиција, така што ќе ја зголемуваме нејзината вредност за 2 секој пат.
  2. Ако паритетот [i] е непарен, тогаш ќе најдеме aj за кој паритет [j] е парен, а потоа ќе ги замениме елементите на i и j.
  3. Овие чекори ќе ги правиме сè додека вредноста на i не е помала од должината на низата паритет.
  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]

Анализа на комплексноста на сортирањето на низата според раствор на лет код за паритет II

Временска сложеност

Временската сложеност на горенаведениот код е Тој) затоа што ја разгледуваме низата паритет само еднаш. Тука n е должината на низата паритет.

Комплексноста на просторот

Комплексноста на просторот на горенаведениот код е О (1) затоа што користиме само променлива за складирање на одговор.

Референци