doc/算法/排序/数字出现次数.md

统计数组中不同元素出现的次数（时间复杂度O(n)，空间复杂度o(1)）

常规思路是利用map进行统计，但不满足时间和空间复杂度的要求； 正确思路： 遍历数组，通过当前元素的值a作为下标，找到下一个元素。最后得到的数组中，下标（因为数组的下标都是从0开始的，所以需要+1）为数组中出现的元素，每个下标对应的值取反输出即是该元素出现的次数。

若当前元素a小于0，则跳过； 若当前元素a大于0，则判断其作为下标对应的元素b是否大于0。 若b大于0，则把b的值赋值给a，并把b置为-1； 若b小于0，则把a置为0，并把b自减1； 注意遍历时，若当前元素为正数依旧处理该当前元素；

// 举例
vector<int> arr = {2, 5, 5, 2, 3};
下标都+1；
/*
1、遍历数组，第一个arr[1]=2，然后看下标为2的元素是arr[2]=5。
2、把arr[2]对应的5赋值给arr[1]，然后arr[2]就设置为-1
3、然后重复整个过程直到结束
它的整个变化过程就是这样
- {2, 5, 5, 2, 3}
- 5, [-1], 5, 2, 3
- 3, [-1], 5, 2, [-1]
- 5, [-1], [-1], 2, [-1]
- [0], [-1], [-1], 2, [-2]
- [0], [-2], [-1], [0], [-2]
这个结果表示：1有0个，2有2个，3有一个，4有0个，5有2个
*/

#include <bits/stdc++.h>

using namespace std;

void sort(vector<int>& nums) {
    int i = 0;
    int n = (int) nums.size();
    while (i < n) {
        int temp = nums[i] - 1;
        if (temp < 0) {
            i++;
            continue;
        }
        if (nums[temp] > 0) {
            nums[i] = nums[temp];
            nums[temp] = -1;
        } else {
            nums[temp]--;
            nums[i] = 0;
        }
    }
}

int main() {
    vector<int> nums{2, 5, 5, 2, 3};
    sort(nums);
    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] < 0)
            cout << i + 1 << " " << (-nums[i]) << endl;
    }
    return 0;
}