半数数字

本文主要是介绍半数数字，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

class Solution {
public:int MoreThanHalfNum_Solution(vector<int> numbers) {map<int, int> map;for (int i : numbers)if (++ map[i] > numbers.size() / 2) return i;return 0;}
};

class Solution {
public:int MoreThanHalfNum_Solution(vector<int> numbers) {vector<int> v1(numbers.size(), 0);for (int i = 0; i<numbers.size(); i++){v1[numbers[i] % numbers.size()]++;}for (int i = 0; i<numbers.size(); i++){if (v1[numbers[i] % numbers.size()]>(numbers.size() / 2)){return numbers[i];}}}
};

class Solution {
public:
void quickSort(vector<int> & numbers, int low, int high){if (low<high){int x = low;int y = high;int ans = numbers[x];while (x<y){while (x<y&&numbers[y]>ans){y--;}if (x<y){numbers[x++] = numbers[y];}while (x<y&&numbers[x]<ans){x++;}if (x<y){numbers[y--] = numbers[x];}numbers[x] = ans;}quickSort(numbers, low, x - 1);quickSort(numbers, x + 1, high);}}int MoreThanHalfNum_Solution1(vector<int> numbers) {vector<int> v(numbers.size(), 0);quickSort(numbers, 0, numbers.size() - 1);int target;int j = 0;v[j]++;for (int i = 1; i<numbers.size(); i++){if (numbers[i] == numbers[0]){v[j]++;if (v[j]>numbers.size() / 2){target = numbers[i];}}else{j++;}}return target;}
};

这篇关于半数数字的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---