Массивті паритеттік II бойынша сұрыптау Leetcode шешімі


Күрделілік дәрежесі оңай
Жиі кіреді Amazon
Array Сұрыптау

Проблеманы шешу

Мәселе бойынша »сұрыптау массиві бойынша Паритет 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 бойынша сұрыптау Leetcode шешімі

Идея: егер біз барлық жұп элементтерді жұп жағдайға қойсақ, онда тақ элементтер автоматты түрде тақ күйінде болады. Сондықтан біз тек жұп элементтерді жұп күйге қалай қою керектігіне ғана назар аударуымыз керек. Біз келесі қадамдарды орындаймыз:

  1. I айнымалысын 0 мен j-ді 1-ден бастаңыз. Мұнда мен тек жұп позицияны орындайтын боламыз, сондықтан біз оның мәнін 2-ге көбейтеміз, ал j тек тақ күйде жүреді, сондықтан оның мәнін 2-ге арттырамыз.
  2. Егер паритет [i] тақ болса, онда біз [j] паритеті болатын aj-ты табамыз, содан кейін элементтерді i және j-ге ауыстырамыз.
  3. Біз i қадамдары паритет массивінің ұзындығынан кіші болғанға дейін жасаймыз.
  4. Паритеттік массивті қайтарыңыз.

Іске асыру

Parity II бойынша сұрыптау массивіне арналған C ++ коды

#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]

Parity II бойынша сұрыптау массивіне арналған Java коды

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 шешімі бойынша сұрыптау массивінің күрделілігін талдау

Уақыт күрделілігі

Жоғарыда келтірілген кодтың уақыт күрделілігі O (N) өйткені біз паритеттік массивті тек бір рет айналып өтеміз. Мұнда n - паритеттік массивтің ұзындығы.

Ғарыштың күрделілігі

Жоғарыда аталған кодтың кеңістігінің күрделілігі мынада O (1) өйткені біз жауап сақтау үшін тек айнымалыны қолданамыз.

Әдебиеттер тізімі