使用 O(n) 的时间复杂度在数组上进行划分。
试了很久的把 >=k 的往后扔,老是不对,结果看了下其他人的思路是把
- int partitionArray(vector < int > &nums, int k) {
- // write your code here
- if (nums.empty()) {
- return 0;
- }
- int index = 0;
- for (int i = 0; i < nums.size(); i++) {
- if (nums[i] < k) {
- swap(nums[i], nums[index]);
- index++;
- }
- }
- return index;
- }
index 是从 0 增加还是有好处的,本来就是要求 >=k 的第一个元素,这样方便很多
来源: http://www.bubuko.com/infodetail-2451673.html