荷蘭國(guó)旗問(wèn)題

給定一個(gè)數(shù)組arr，和一個(gè)數(shù)num，請(qǐng)把小于num的數(shù)放在數(shù)組的左邊，等于num的數(shù)放在數(shù)組的中間，大于num的數(shù)放在數(shù)組的右邊
要求額外空間復(fù)雜度O（1），時(shí)間復(fù)雜度O（N）

思路

使用兩個(gè)指針來(lái)標(biāo)記小于num部分和大于num部分
less指向小于num部分最后一位
more指向大于num部分的第一位
cur指向當(dāng)前位置
分三種情況：
（1）當(dāng)arr[cur] > num時(shí)，交換arr[cur] 和 arr[–more]，cur保持不變
（2）當(dāng)arr[cur] < num時(shí)，交換arr[cur]和arr[++less]，cur++
（3）當(dāng)arr[cur] = num時(shí)，cur++

代碼

#include <bits/stdc++.h> using namespace std;inline void swap(int arr[], int i, int j);int* partition(int arr[], int L, int R, int num){int less = L-1;int more = R+1;int cur = L;while(cur < more){if(arr[cur] > num){swap(arr, --more, cur);}else if (arr[cur] < num){swap(arr, ++less, cur++);}else{cur++;}}return new int [2] {less, more}; }inline void swap(int arr[], int i, int j){int temp = arr[i];arr[i] = arr[j];arr[j] = temp; }inline void outputArr(int arr[], int L, int R){for(int i = L; i <= R; i++){cout << arr[i] << " ";}cout << endl; }int main(){int num;int arr[10] = {2,4,8,9,4,3,2,1,6,8};int *result;cin >> num;outputArr(partition(arr, 0, 9, num), 0, 1);outputArr(arr, 0, 9); }

相關(guān)問(wèn)題

荷蘭國(guó)旗問(wèn)題是實(shí)現(xiàn)快速排序的基本思想，對(duì)于理解快速排序有重要意義
快速排序的實(shí)現(xiàn)可以參考這篇文章：
隨機(jī)快速排序

總結(jié)

以上是生活随笔為你收集整理的C/C++实现荷兰国旗问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。