题目描述:
给定一个数组 arr, 和一个数 num, 请把小于 num 的数放在数组的左边, 等于 num 的数放在数组的中间, 大于 num 的数放在数组的右边. 要求额外空间复杂度 O(1), 时间复杂度 O(N)
解题思路:
使用两个指针: p1,p2
- p1 = -1; // 左指针, 在 p1 左边并含 p1 的所有数都 < num
- p2 = N ; // 右指针, p2=N 在 p2 的右边含 p2 的所有数都大于 num
然后比较 arr 与 num 的值, 并与相应的 p1,p2 的位置交换
代码实现:
- #include <iostream>
- using namespace std;
- void swap(int& a, int &b)
- {
- int temp;
- temp = a;
- a = b;
- b = temp;
- }
- // 记住, 单次遍历 n(n <<N) 次数组的时间复杂度 = n*O(N) == O(N)
- template<class T>// 目前我只想到了使用模板来实现引用数组, 其他的引用方法都报错了.
- void Test(T& array , const int num)
- {
- int N, p1, p2;// 两个指针
- p1 = -1;// 左指针, 在 p1 左边并含 p1 的所有数都 < num
- p2 = N = sizeof(array) / sizeof(array[0]);// 右指针, p2=N 在 p2 的右边含 p2 的所有数都大于 num
- for (int i = 0; i != p2; )
- {
- if (array[i] <num)
- swap(array[++p1], array[i++]);
- else if (array[i]> num)
- swap(array[--p2], array[i]);
- else
- ++i;
- }
- }
- void Heland()
- {
- int arr[] = { 1, 5,7,4,6,4,2,9 };
- Test(arr, 4);
- for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i)
- cout << arr[i] << " ";
- cout << endl << "**************************" << endl;
- }
来源: https://www.cnblogs.com/zzw1024/p/10987751.html