Paritet II Leetcode Həlli ilə Sıralama Array

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon
alqoritmlər Geyim kodlaşdırma müsahibə müsahibə hazırlığı LeetCode LeetCodeSolutions çeşidləyiciBaxılıb 74

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

Problemdə ”Sıralama Array By Parite II, ”bizə bütün elementlərin müsbət tam ədədi olduğu bir paritet sıra verilir. Dizidə cüt sayda element var. Dizidə bərabər sayda cüt və tək element var.

Bizim vəzifəmiz massivin elementlərini elə düzəltməkdir ki, paritet [i] cüt elementi ehtiva etsin, i başqa cür olduqda paritet [i] tək bir element içərsin və sonra yeni massivi geri qaytarsın.

misal

parity=[1,2,3,4]
[2,1,4,3]

Explanation:  Şərti təmin edən bütün mümkün sıra bunlardır: [2,1,4,3], [2,3,4,1], [4,1,2,3], [4,3,2,1]. Bu sıra hər kəs doğru cavabdır.

Paritet II Leetcode Həlli ilə Sort Array üçün yanaşma

Bu problemə ilk və əsas yanaşma yeni bir sıra yaratmaq və sonra köhnə massivi keçməkdir. Cüt bir elementlə qarşılaşdığımız zaman onu yeni massivin cüt vəziyyətinə, tək bir elementlə qarşılaşdığımız zaman onu yeni massivin tək vəziyyətinə qoyduq. Bu yanaşma əlavə yerdən istifadə edir və yerin yenidən tənzimlənməsindən istifadə edərək məntiqimizi inkişaf etdirə bilərik.

Paritet II Leetcode Həlli ilə Sıralama ArrayPin

Fikir budur ki, bütün cüt elementləri cüt vəziyyətə qoysaq, tək elementlər avtomatik olaraq tək vəziyyətdə olacaq. Beləliklə, yalnız elementləri bərabər vəziyyətdə necə qoyacağımıza diqqət yetirməliyik. Bu addımları izləyəcəyik:

  1. I dəyişənini 0 və j ilə 1 ilə başlayın. Burada yalnız bərabər mövqedə hərəkət edəcəyəm, beləliklə hər dəfə dəyərini 2 artıracağıq və j yalnız tək mövqedə hərəkət edəcəyik, buna görə hər dəfə dəyərini 2 artıracağıq.
  2. Paritet [i] təkdirsə, [j] bərabərliyinin bərabər olduğu aj-ı tapacağıq və sonra i və j-də elementləri dəyişdirəcəyik.
  3. Bu addımları i dəyəri paritet sıra uzunluğundan kiçik olana qədər edəcəyik.
  4. Paritet dizisini qaytarın.

Həyata keçirilməsi

Parity II tərəfindən Sort Array üçün C ++ kodu

#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 tərəfindən Sort Array üçün Java kodu

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]

Paritet II Leetcode Həlli ilə Sort Dizisinin Mürəkkəblik Analizi

Zaman mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (n) çünki biz yalnız bir dəfə paritet cərgədən keçirik. Burada n cütlük massivinin uzunluğu.

Kosmik mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (1) çünki cavabı saxlamaq üçün yalnız dəyişəndən istifadə edirik.

References

Crack Sistemi Dizayn Müsahibələri
Translate »