Вопрос:

Ссылка: https://practice.geeksforgeeks.org/problems/arranging-the-array1131/1

Вам дан массив размером N. Перестройте заданный массив на месте таким образом, чтобы все отрицательные числа стояли перед всеми неотрицательными числами.
(Сохраняйте порядок всех -ve и неотрицательных чисел, указанный в исходном массиве).

Пример 1:

Input:
N = 4
Arr[] = {-3, 3, -2, 2}
Output:
-3 -2 3 2
Explanation:
In the given array, negative numbers
are -3, -2 and non-negative numbers are 3, 2.

Пример 2:

Input:
N = 4
Arr[] = {-3, 1, 0, -2}
Output:
-3 -2 1 0
Explanation:
In the given array, negative numbers
are -3, -2 and non-negative numbers are 1, 0.

Ваша задача.
Вам не нужно ничего читать или печатать. Ваша задача — завершить функцию Rearrange(), которая принимает массив Arr[] и его размер N в качестве входных данных и возвращает массив после перестановки с пробелами между элементами массива.

Ожидаемая временная сложность: O(N. Log(N))
Ожидаемое вспомогательное пространство: O(Log(N))

Ограничения:
1 ≤ N ≤ 105
-109 ≤ Элементы массива ≤ 109

Решение:

Код:

class Solution
{
    public:
        void Rearrange(int arr[], int n)
        {
            // Your code goes here
            vector<int> a;
            vector<int> b;
            for(int i=0; i<n; i++){
                if(arr[i]<0){
                    a.push_back(arr[i]);
                }else{
                    b.push_back(arr[i]);
                }
            }
            
            int k=0;
            for(auto i : a){
                arr[k++] = i;
            }
            
            for(auto i : b){
                arr[k++] = i;
            }
        }
};

Временная сложность: O(N)

Космическая сложность: O(N)

  1. Создайте два пустых вектора, a и b, для хранения отрицательных и положительных чисел соответственно.
  2. Перебрать заданный массив arr с помощью цикла.
  3. Если текущий элемент arr[i] отрицателен (меньше нуля), вставьте его в вектор a.
  4. В противном случае, если текущий элемент arr[i] неотрицательный (больше или равен нулю), поместите его в вектор b.
  5. Инициализируйте переменную k значением 0, которое будет использоваться в качестве индекса для обновления исходного массива.
  6. Переберите элементы в векторе a, используя цикл for на основе диапазона.
  7. Назначьте каждому элементу i из вектора a k-ю позицию в исходном массиве arr.
  8. Увеличьте k на 1.
  9. Переберите элементы в векторе b, используя цикл for на основе диапазона.
  10. Назначьте каждому элементу i из вектора b k-ю позицию в исходном массиве arr.
  11. Увеличьте k на 1.
  12. Исходный массив arr теперь переупорядочивается таким образом, что все отрицательные числа появляются перед положительными числами.

Заключение:

Надеюсь, что решение окажется полезным и вам, ребята, понравилось. Давайте обсудим новые подходы. Пожалуйста, прокомментируйте, если у вас есть предложения и сомнения, которые необходимо развеять.