Fork me on GitHub

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

问题描述:

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

思路:

  • 从第一个元素开始遍历,每遍历到一个元素,将(该元素值 - 1 记为index)作为一个下标值,令该下标对应的元素值为元素 index+1出现的次数。
  • 若下标index为负值,说明该元素已经处理过,跳过;
  • 判断,若a[index]为正,则赋初值-1;若为负,则执行减1操作。
  • 最后,数组中存储的元素即为统计次数,而该元素对应的下标+1即为元素值。
    Count-the-number-of-occurrences.cpplink
    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
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    #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;
    }
您的支持将鼓励我继续创作!