Ταξινόμηση Array κατά Parity II Λύση κωδικού πρόσβασης


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα
Παράταξη Ταξινόμηση

Δήλωση προβλήματος

Στο πρόβλημα "Ταξινόμηση Array By Ισοτιμία II, "μας δίνεται ένας πίνακας ισοτιμίας όπου όλα τα στοιχεία είναι θετικοί ακέραιοι. Ο πίνακας περιέχει έναν ομοιόμορφο αριθμό στοιχείων. Ο πίνακας περιέχει ίσο αριθμό ζυγών και μονών στοιχείων.

Το καθήκον μας είναι να αναδιατάξουμε τα στοιχεία του πίνακα με τέτοιο τρόπο ώστε η ισοτιμία [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]. Οποιοσδήποτε από αυτούς τους πίνακες είναι σωστή απάντηση.

Προσέγγιση για το Sort Array By Parity II Leetcode Solution

Η πρώτη και βασική προσέγγιση σε αυτό το πρόβλημα είναι να δημιουργήσετε έναν νέο πίνακα και στη συνέχεια να διασχίσετε τον παλιό πίνακα. Όταν συναντήσουμε ένα ζυγό στοιχείο, βάλτε το στη ζυγή θέση του νέου πίνακα και όταν συναντήσετε ένα περίεργο στοιχείο, τοποθετήστε το στη μονή θέση του νέου πίνακα. Αυτή η προσέγγιση χρησιμοποιεί επιπλέον χώρο και μπορούμε να βελτιώσουμε τη λογική μας χρησιμοποιώντας την αναδιάταξη.

Ταξινόμηση Array κατά Parity II Λύση κωδικού πρόσβασης

Η ιδέα είναι εάν βάλουμε όλα τα ομοιόμορφα στοιχεία σε ομοιόμορφη θέση, τότε τα περίεργα στοιχεία θα βρίσκονται αυτόματα σε περίεργη θέση. Επομένως, πρέπει να επικεντρωθούμε μόνο στον τρόπο τοποθέτησης ομοιόμορφων στοιχείων σε ομαλή θέση. Θα ακολουθήσουμε αυτά τα βήματα:

  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 για Sort Array By Parity 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]

Ανάλυση πολυπλοκότητας του Sort Array By Parity II Leetcode Solution

Χρόνος πολυπλοκότητας

Η χρονική πολυπλοκότητα του παραπάνω κώδικα είναι O (n) γιατί διασχίζουμε τον πίνακα ισοτιμίας μόνο μία φορά. Εδώ είναι το μήκος του πίνακα ισοτιμίας.

Διαστημικότητα

Η πολυπλοκότητα του παραπάνω κώδικα είναι Ο (1) γιατί χρησιμοποιούμε μόνο μια μεταβλητή για να αποθηκεύσουμε την απάντηση.

αναφορές