3467.Transform Array by Parity

Ссылка на задачу: https://leetcode.com/problems/transform-array-by-parity/description/

Описание

Дан массив целых чисел nums. Необходимо трансформировать nums, следуя следующим операциям в указанном порядке:

1. Заменить все четные числа на 1

2. Заменить все нечетные числа на 0

3. Отсортировать модифицированный массив в порядке неубывания

Верните модифицированный массив в качестве результата.

Примеры

Пример 1

Input:

Output:

Объяснение:

• меняем все четные числа на 0 (элементы 4 и 2), а также нечетные на 1 (элементы 3 и 1): [0, 1, 0, 1]

• сортируем модифицированный массив: [0, 0, 1, 1]

Пример 2

Input:

Output:

Объяснение:

• меняем все четные числа на 0 (элементы 4 и 2), а также нечетные на 1 (элементы 3, 5 и 1): [1, 1, 1, 0, 0]

• сортируем модифицированный массив: [0, 0, 1, 1, 1]

Ограничения

• 1 <= nums.length <= 100

• 1 <= nums[i] <= 1000

Решение

Способ 1

Решение кроется в условии задачи, достаточно пробежаться по всему массиву, выполняя одновременно шаги 1 и 2, а затем отсортировать модифицированный массив.

Алгоритм:

1. Итерируемся по всему массиву

2. Выполяем шаги 1 и 2

3. Сортируем массив

Код:

python

class Solution:
    def transformArray(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            if nums[i] % 2 == 0:
                nums[i] = 0
            else:
                nums[i] = 1
        nums.sort()
        return nums

C++

class Solution {
public:
    vector<int> transformArray(vector<int>& nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] % 2 == 0) {
                nums[i] = 0;
            } else {
                nums[i] = 1;
            }
        }
        sort(nums.begin(), nums.end());
        return nums;
    }
};

Сложность алгоритма по времени - O(N+N*logN)

Две операции: итерация по массиву размером N для модификации в соответствии с шагами 1 и 2; сортировка (встроенные методы сортировки языков python и C++ имеют сложность NlogN). В результате имеем O(N + N*logN).

Сложность алгоритма по памяти - О(1)

Для решения не требуются никакие дополнительные объекты.

Способ 2

Можно обойтись без сортировки, которая является относительно дорогой. После сортировки массива сначала будет идти m нулей, а затем - k единиц, так как больше вариантов нет (числа в массиве либо четные, либо нечетные). Так, достаточно знать либо m, либо k (второе может быть найдено путем вычитания из N), после чего заменить первые m элементов массива нулями, а следующие k - единицами.

Алгоритм:

1. Итерируемся по массиву, считая количество четных элементов m

2. Определяем количество нечетных элементов k как N - m

3. Первые m элементов массива заменяем нулями, следующие k - единицами

Код:

python

class Solution:
    def transformArray(self, nums: List[int]) -> List[int]:
        even_cnt = 0

        for i in range(len(nums)):
            if nums[i] % 2 == 0:
                even_cnt += 1
        
        for i in range(even_cnt):
            nums[i] = 0
        
        for i in range(even_cnt, len(nums)):
            nums[i] = 1

        return nums

C++

class Solution {
public:
    vector<int> transformArray(vector<int>& nums) {
        int even_cnt = 0;

        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] % 2 == 0) {
                ++even_cnt;
            }
        }

        for (int i = 0; i < even_cnt; ++i) {
            nums[i] = 0;
        }

        for (int i = even_cnt; i < nums.size(); ++i) {
            nums[i] = 1;
        }
        return nums;
    }
};

Сложность алгоритма по времени - O(N)

В данном случае мы итерируемся по массиву размером N дважды. Во-первых, для определения количества четных элементов. Во-вторых, для замены элементов массива (два цикла m и k, которые в сумме равны N).

Сложность алгоритма по памяти - O(1).

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