Сортировка массива по четности II Решение Leetcode


Сложный уровень Легко
Часто спрашивают в Амазонка
массив Сортировка

Постановка задачи

В задаче »Сортировать массив по паритет 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]. Любой из этих массивов является правильным ответом.

Подход к решению Leetcode для сортировки массива по четности II

Первый и основной подход к этой проблеме - создать новый массив, а затем пройти по старому массиву. Когда мы встречаем четный элемент, помещаем его в четную позицию нового массива, а когда мы встречаем нечетный элемент, помещаем его в нечетную позицию нового массива. Этот подход использует дополнительное пространство, и мы можем улучшить нашу логику, используя перестановку по месту.

Сортировка массива по четности II Решение Leetcode

Идея в том, что если мы поместим все четные элементы в четную позицию, то нечетные элементы автоматически будут в нечетной позиции. Так что нам нужно только сосредоточиться на том, как поставить четные элементы в четное положение. Мы будем следовать этим шагам:

  1. Инициализируйте переменную i с помощью 0 и j с помощью 1. Здесь i будет перемещаться только по четной позиции, поэтому мы будем увеличивать ее значение на 2 каждый раз, а j будет перемещаться только по нечетной позиции, поэтому мы будем увеличивать ее значение на 2 каждый раз.
  2. Если четность [i] нечетная, то мы найдем j, для которого четность [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]

Анализ сложности решения для сортировки массива по четности II Leetcode

Сложность времени

Временная сложность приведенного выше кода О (п) потому что мы обходим массив четности только один раз. Здесь n - длина массива четности.

Пространство сложности

Пространственная сложность приведенного выше кода равна O (1) потому что мы используем только переменную для хранения ответа.

дело