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

 

一个长度大小为n的数组，数组中的每个元素的取值范围在[1,n]，且为正整数。

 

问：如何在时间复杂度为O(n)，空间复杂度为O(1)的条件下，统计数组中不同元素出现的次数。

 

思路：数组按序扫描，通过当前元素的值作为下标，找到下一个元素。最后得到的数组中，下标（因为下标从0开始的，故输出时需要+1）为数组中出现的元素，每个下标对应的值取反输出即是该元素出现的频率。

 

若当前元素小于0，

 

        则跳过；

 

若当前元素大于0，

 

        则判断其作为下标索引到的元素是否大于0，

 

                若大于0，则索引到的元素赋值给当前元素，索引到的元素置为-1；

 

                若小于0，则索引到的元素自减1，当前元素置为0；

 

代码如下：

 

 

#include <iostream>   
#include <algorithm>   
#include <vector>   
#include <queue>  
#include <stack>  
#include <string>   
#include <string.h>   
#include <fstream>   
#include <map>   
#include <iomanip>   
#include <cstdio>   
#include <cstdlib>  
#include <cmath>  
#include <deque>  
#include <hash_map>  
  
using namespace std;   
  
const int MAX = 0x7FFFFFFF;   
const int MIN = 0x80000000;   
  
void work(int a[], int n)  
{  
    int i = 0;  
    while(i < n)  
    {  
        int temp = a[i] - 1;  
        if(temp < 0)  
        {  
            i++;  
            continue;  
        }  
        if(a[temp] > 0)  
        {  
            a[i] = a[temp];  
            a[temp] = -1;  
        }  
        else  
        {  
            a[temp]--;  
            a[i] = 0;  
        }  
    }  
}  
  
int main()  
{  
    int n;  
    while(cin >> n)  
    {  
        int *a = new int[n];  
        for(int i = 0; i < n; i++)  
            cin >> a[i];  
        work(a, n);  
        for(int i = 0; i < n; i++)  
            if(a[i] < 0)  
                cout << i + 1 << " " << (-a[i]) << endl;  
        cout << "********************" << endl;  
        delete[] a;  
    }  
    system("pause");  
    return 0;  
}  

 

 

补充：软件开发 , C++ ,