问题

题目来源: https://leetcode-cn.com/problems/find-majority-element-lcci/
数组中占比超过一半的元素称之为主要元素。给定一个整数数组，找到它的主要元素。若没有，返回-1。

题解

复杂度: 空间复杂度O(n) 时间复杂度O(n)
思路:
最开始想使用hashmap来保持O(1)的查找，但是leetcode不让使用hashmap.于是只能自己近似一个O(1)查找的算法。
对某个区间的数，开辟一个数组来统计它的个数，相当于counter
在这个例子中，我开辟了一个长度为1000的数组counter，初始化为0，counter[500+i]保存数i在传入数据中的个数。
这样对于-500 到500这个区间的数，查找他的个数时间复杂度为O(1).
对于这个区间外的数，我使用一个map来管理他的查找。只要这一区间的数在输入数据中是极小部分的，那么我的查找时间就近似O(1)的。
cpp代码:

  1. class Solution {
  2. public:
  3.     int majorityElement(vector<int>& nums) {
  4.         int counter[1000] = {0};
  5.         vector<int> :: iterator  iter;
  6.         int size = 0;
  7.         int majority_val ;
  8.         int majority_num = 0;
  9.         map<int,int> counter2;
  10.         for(iter = nums.begin(); iter != nums.end(); iter ++){
  11.             int this_integer_num;
  12.             if(*iter > 500 or *iter < -500){
  13.                 if(counter2.find(*iter) == counter2.end())
  14.                     {counter2[*iter] = 0;}
  15.                 this_integer_num = counter2[*iter] + 1;
  16.                 counter2[*iter] = this_integer_num;
  17.             }
  18.             else{
  19.                 this_integer_num = counter[*iter + 500] + 1;
  20.                 counter[*iter+500] = this_integer_num;
  21.             }
  22.             if(this_integer_num > majority_num){
  23.                 majority_num = this_integer_num;
  24.                 majority_val = * iter;
  25.             }
  26.             size ++;
  27.         }
  28.         if(majority_num > size / 2){return majority_val;}
  29.         return -1;
  30.     }
  31. };

image.png
可以看出对大部分测试用例保持了良好的时间与速度
一些加快速度的要点:

  1. 在cpp中，使用迭代器的速度来遍历整个容器速度是最块的。尤其是对大量级数据。速度差异会非常明显。
  2. 对于大量数据而言，保持O(1)的查找速度是最优的。这意味着你的查找速度不会随着数据量的变化而变化。思想就是，通过一种映射，让你直接知道或者计算出你想要查找的数据的地址是在哪里。hash表能做到这点。他把你要查找的键通过hash函数映射为一个地址，而这道题中我开辟一个数组来存储查找的结果，直接使用它本身的值作为下标来查找结果，都是利用了这个思想。