вчера был 49 день кодирования. вчера решил одну задачу
Проблема: чередование положительных и отрицательных чисел
Дан несортированный массив Arr из N положительных и отрицательных чисел. Ваша задача состоит в том, чтобы создать массив чередующихся положительных и отрицательных чисел, не изменяя относительный порядок положительных и отрицательных чисел.
Примечание. Массив должен начинаться с положительного числа.
Пример 1:
Input: N = 9 Arr[] = {9, 4, -2, -1, 5, 0, -5, -3, 2} Output: 9 -2 4 -1 5 -5 0 -3 2 Explanation : Positive elements : 9,4,5,0,2 Negative elements : -2,-1,-5,-3 As we need to maintain the relative order of postive elements and negative elements we will pick each element from the positive and negative and will store them. If any of the positive and negative numbers are completed. we will continue with the remaining signed elements.The output is 9,-2,4,-1,5,-5,0,-3,2.
Пример 2:
Input: N = 10 Arr[] = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8} Output: 5 -5 2 -2 4 -8 7 1 8 0 Explanation : Positive elements : 5,2,4,7,1,8,0 Negative elements : -5,-2,-8 As we need to maintain the relative order of postive elements and negative elements we will pick each element from the positive and negative and will store them. If any of the positive and negative numbers are completed. we will continue with the remaining signed elements.The output is 5,-5,2,-2,4,-8,7,1,8,0.
Ваша задача:
Вам не нужно читать ввод или печатать что-либо. Ваша задача — завершить функцию rearrange(), которая принимает в качестве параметров массив целых чисел arr[]иn. Вам нужно изменить сам массив.
Ожидаемая временная сложность: O(N)
Ожидаемое вспомогательное пространство: O(N)
Решение (в Java):
class Solution { void rearrange(int arr[], int n) { List<Integer> pos= new ArrayList<>(); List<Integer> neg= new ArrayList<>(); for(int i=0; i<n; i++){ if(arr[i]>=0) pos.add(arr[i]); if(arr[i]<0) neg.add(arr[i]); } int i=0,j=0 ,k=0; while(j<pos.size() && k<neg.size()){ arr[i++]=pos.get(j++); arr[i++]=neg.get(k++); } while(j<pos.size()) arr[i++]=pos.get(j++); while(k<neg.size()) arr[i++]=neg.get(k++); } }