统计数组中各元素出现次数

问题描述：

• 给定一个整数数组a，长度为N，元素取值范围为[1,N]。
• 统计各个元素出现的次数，要求时间复杂度为O(N)，空间复杂度为O(1)。
• 可以改变原来数组结构。

思路：

• 从第一个元素开始遍历，每遍历到一个元素，将（该元素值 - 1 记为index）作为一个下标值，令该下标对应的元素值为元素 index+1出现的次数。
• 若下标index为负值，说明该元素已经处理过，跳过；
• 判断，若a[index]为正，则赋初值-1；若为负，则执行减1操作。
• 最后，数组中存储的元素即为统计次数，而该元素对应的下标+1即为元素值。

  Count-the-number-of-occurrences.cpplink

  #include <iostream>
  #include <vector>
  using namespace std;
  void count(vector<int> &nums)
  {
      // TODO Auto-generated method stub
      int n = nums.size();
      int i = 0;
      //采用while循环
      while (i < n)
      {
          //由于元素取值范围为[1,N]，因此，可以将（当前元素值-1）作为下标值，找到相应位置处的元素，将其存储的值作为-times，因为原来存储值都为正值，为防止混淆，用负值存储
          int temp = nums[i] - 1;
          if (temp < 0)
          { //表示该元素已经处理过了，跳过
              i++;
              continue;
          }
          else if (nums[temp] > 0)
          {                         //第一次处理一个值
              nums[i] = nums[temp]; //暂存新元素
              nums[temp] = -1;
          }
          else
          { //已经不是第一次处理该值了
  
              nums[i] = 0; //没有新的元素要处理，置0
              nums[temp]--;
          }
      }
  
      for (int j = 0; j < n; ++j)
      {
          cout << j + 1 << "," + -nums[j] << "\t";
      }
  }
  
  int main(int argc, char const *argv[])
  {
      vector<int> test{6, 2, 4, 1, 2, 5};
      count(test);
      return 0;
  }