Сартаванне масіва па рашэнні цэтліка II


Узровень складанасці Лёгка
Часта пытаюцца ў амазонка
масіў сартаванне

Пастаноўка праблемы

У задачы ”Сартаваць масіў па парытэт II », мы атрымліваем масіў парытэту, дзе ўсе элементы з'яўляюцца натуральнымі лікамі. Масіў утрымлівае цотную колькасць элементаў. Масіў змяшчае роўную колькасць цотных і няцотных элементаў.

Наша задача - пераставіць элементы масіва такім чынам, каб parity [i] утрымлівала цотны элемент, калі i нават у адваротным выпадку parity [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]. Любы з гэтых масіваў з'яўляецца правільным адказам.

Падыход для сартавання масіва па рашэнні чысловага кода Parity 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]

Код 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

Часовая складанасць

Часавая складанасць вышэйзгаданага кода Аб (п) таму што мы праходзім масіў парытэту толькі адзін раз. Тут n - даўжыня масіву парытэту.

Касмічная складанасць

Касмічная складанасць вышэйзгаданага кода складаецца ў O (1) таму што мы выкарыстоўваем толькі зменную для захоўвання адказу.

Спасылкі