資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 在 O(1) 空間複雜度內重排陣列，使其正負數交替排列
給定一個包含正數和負數的整數型別陣列，例如任意大小的 arr[]。任務是重排陣列，使其正數被負數包圍。如果正數和負數數量不一致，則多餘的數將排列在陣列的末尾。
讓我們看看這個任務的不同輸入輸出場景：
輸入 - int arr[] = {-1, -2, -3, 1, 2, 3}
輸出 - 陣列重排前：-1 -2 -3 1 2 3 使用 O(1) 額外空間在陣列中交替排列正負數的結果是：-1 1 -2 2 -3 3
解釋 - 我們得到一個大小為 6 的整數陣列，包含正數和負數元素。現在，我們將重排陣列，使所有正數被負數包圍，所有多餘的元素都新增到陣列的末尾，即 -1 1 -2 2 -3 3 將是最終結果。
輸入 - int arr[] = {-1, -2, -3, 1, 2, 3, 5, 5, -5, 3, 1, 1};
輸出 - 陣列重排前：-1 -2 -3 1 2 3 5 5 -5 3 1 1 使用 O(1) 額外空間在陣列中交替排列正負數的結果是：-1 1 -2 2 -3 3 -5 5 5 3 1 1
解釋 - 我們得到一個大小為 12 的整數陣列，包含正數和負數元素。現在，我們將重排陣列，使所有正數被負數包圍，所有多餘的元素都新增到陣列的末尾，即 -1 1 -2 2 -3 3 -5 5 5 3 1 1 將是最終結果。
下面程式中使用的方案如下
輸入一個整數型別元素的陣列並計算陣列的大小。
使用 FOR 迴圈列印執行重排操作之前的陣列。
呼叫函式 Rearrangement(arr, size)，並將陣列和陣列大小作為引數傳遞。
在函式 Rearrangement(arr, size) 內部
宣告一個整數變數 'ptr' 並將其初始化為 -1。
從 i 為 0 開始迴圈到 i 小於 size。在迴圈內部，檢查 IF ptr 大於 0，然後檢查 IF arr[i] 大於 0 並且 arr[ptr] 小於 0 或 arr[i] 小於 0 並且 arr[ptr] 大於 0，然後呼叫函式 move_array(arr, size, ptr, i) 並檢查 IF i - ptr 大於 2，則將 ptr 設定為 ptr + 2。否則，將 ptr 設定為 -1。
檢查 IF ptr 為 -1，然後檢查 arr[i] 大於 0 並且 !(i & 0x01) 或 (arr[i] 小於 0) 並且 (i & 0x01)，則將 ptr 設定為 i。
在函式 move_array(int arr[], int size, int ptr, int temp) 內部
宣告一個字元型別的變數 'ch' 並將其設定為 arr[temp]。
從 i 為 temp 開始迴圈到 i 大於 ptr。在迴圈內部，將 arr[i] 設定為 arr[i - 1]。
將 arr[ptr] 設定為 ch。
示例
#include <iostream>
#include <assert.h>
using namespace std;
void move_array(int arr[], int size, int ptr, int temp){
char ch = arr[temp];
for(int i = temp; i > ptr; i--){
arr[i] = arr[i - 1];
}
arr[ptr] = ch;
}
void Rearrangement(int arr[], int size){
int ptr = -1;
for(int i = 0; i < size; i++){
if (ptr >= 0){
if(((arr[i] >= 0) && (arr[ptr] < 0)) || ((arr[i] < 0) && (arr[ptr] >= 0))){
move_array(arr, size, ptr, i);
if(i - ptr >= 2){
ptr = ptr + 2;
}
else{
ptr = -1;
}
}
}
if(ptr == -1){
if (((arr[i] >= 0) && (!(i & 0x01))) || ((arr[i] < 0) && (i & 0x01))){
ptr = i;
}
}
}
}
int main(){
//input an array
int arr[] = {-1, -2, -3, 1, 2, 3};
int size = sizeof(arr) / sizeof(arr[0]);
//print the original Array
cout<<"Array before Arrangement: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
//calling the function to rearrange the array
Rearrangement(arr, size);
//print the array after rearranging the values
cout<<"\nRearrangement of an array in alternating positive & negative items with O(1) extra space is: ";
for(int i = 0; i < size; i++){
cout<< arr[i] << " ";
}
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出
Array before Arrangement: -1 -2 -3 1 2 3 Rearrangement of an array in alternating positive & negative items with O(1) extra space is: -1 1 -2 2 -3 3
609 次瀏覽
