自然数数组的排序
一、题目
给定一个长度为 N 的整形数组 arr，其中有 N 个互不相等的自然数 1 – N。请实现 arr 的排序，但是不要把下标0 – N−1 位置上的数通过直接赋值的方式替换成1 – N
二、思路
此题目比较简单。数组长度为 N，存储的元素是 1 – N，但是是乱序的。我们想要的结果是：
arr[i] = i+1 这个表达式成立，因此我们遍历这个数组，遇到表达式成立的，直接跳过；遇到表达式不成立的，我们进行交换，把当前位置的元素和这个元素应该出现的位置处的元素进行交换，交换完继续判断表达式是否成立。直到数组遍历完成
三、代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <vector>
#include <iostream>
#include <algorithm>
class Solution {
public:
void sort_01(std::vector<int>& arr) {
int i = 0;
for (; i < arr.size();) {
if (arr[i] == i+1) {
i++;
} else {
std::swap(arr[i], arr[arr[i]-1]);
}
}
}
};
void print_arr(const std::vector<int>& arr) {
for (const auto x : arr) {
std::cout << x << " ";
}
std::cout << std::endl;
}
int main() {
Solution s;
std::vector<int> arr{2,1,4,5,3};
s.sort_01(arr);
print_arr(arr);
return 0;
}
|
时间复杂度是：O(n)