牛客的刷题之路不停歇 ⌓‿⌓

  不积跬步无以至千里，不积小流无以成江海

  The harder you work,the luckier you will be  

---

题目及示例

题目链接

描述

    给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

    例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：n≤50000n≤50000，数组中元素的值 0≤val≤100000≤val≤10000

要求：空间复杂度：O(1)O(1)，时间复杂度 O(n)O(n)

输入描述

    保证数组输入非空，且保证有解

样例

---

题目解读

    查找数组中元素数量超过整个数组元素数量一半的元素

    可通过记录每个元素出现的次数来实现相应问题的查找

---

方法一（取巧的解决方法）：

思路：

    已知，数组非空，且一定有解，那就一定有一个元素的数量超过一半，我们只需要通过对数组进行排序，然后取中间值即可

思路说明：
如数组 { 1，5，7，2，2，2，2，2}排序后为{1，2，2，2，2，2，5，7}

再如数组{1，3，5，5，5，5，4}排序后为{1，3，4，5，5，5，5}

因为该元素的数量超过整个数组数量的一半，所以其不管大小，排序后必定经过数组中心

 核心代码：

int MoreThanHalfNum_Solution(vector<int>& numbers) {sort(numbers.begin(),numbers.end());return numbers[numbers.size()/2];}

---

方法二（哈希表）：

思路：

    通过哈希表记录每个元素的出现个数，当达到目标时返回答案即可

• 先构建一个map容器用于哈希表
• 通过 for 循环对每个元素进行试探
• 通过对map容器的应用进行对其进行++操作
• 当容器中有元素的数量到达目标时，直接返回答案

核心代码：

int MoreThanHalfNum_Solution(vector<int>& numbers) {unordered_map<int,int> hx;for(int i=0;i<numbers.size();i++){hx[numbers[i]]++;if(hx[numbers[i]] > numbers.size()/2){                               return numbers[i];}                         }                                                                         return 0;}

---

希望能给你提供一下参考思路

✿✿ヽ(°▽°)ノ✿