首页 > 代码库 > 【原创】leetCodeOj --- Majority Element 解题报告(脍炙人口的找n个元素数组中最少重复n/2次的元素)
【原创】leetCodeOj --- Majority Element 解题报告(脍炙人口的找n个元素数组中最少重复n/2次的元素)
题目地址：
https://oj.leetcode.com/problems/majority-element/
题目内容：
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.
You may assume that the array is non-empty and the majority element always exist in the array.
方法：
要求有两个：
0、时间复杂度是O(N)
1、空间复杂度是O(1) // 这个是当然的，否则来一个hashmap，谁不会 = _ =!
要点是维护这么一个性质：
首先，不妨假设目标元素出现了a次，而总共有b个元素，那么：
b/a <= 1/2
我们可以设定两个指针，一个指向头部，一个指向尾部。要点在于维护这么一个性质：首尾指针之间的数组，目标元素数量占全部数量的1/2下取整之上。如果两个指针指向的元素不相等，说明此时至少有一个指针指向的元素不是所要求的元素，因此，我们可以抛弃这两个元素，这个时候目标元素在源数组中的比率不会降低。
证明就比较简单了。假设最坏的情况，有一个是目标元素，另一个不是，则有：
b/a < (b-1)/(a-2)，当2b <= a时成立。而2b <= a是题目给出的条件。
那么如果两个元素相等呢？我们还能抛弃这两个元素吗？回答是不能。因为(b-1)/(a-1) < b/a，不能维持目标元素在原数组中比率不降低的性质。
那该怎么办？答案是维护一个指向当前元素【下一个不相等】的指针，如果相等，那么和下一个和自己不相等的元素交换位置即可。这个指向下一个不相等的指针只会往前走，因此，最多走n次。而我们总共维护4个指针，最多O(4n)，还是O(n)。
下面是具体代码：
class Solution {public: int majorityElement(vector<int> &num) { int start = 0; int fin = num.size() - 1; int startnxt = findNextStart(start,num,start); //找到下一个和start不等的指针。 int finnxt = findNextFin(fin,num,fin); while (start < fin) { if (num[start] == num[fin]) { if (startnxt >= finnxt) // 若当前首尾指针指向的数据相等，那么下轮操作后之间的数据就全部相等了，故可以直接返回结果。 return num[start]; swap(&num[start],&num[startnxt]); } start ++; fin --; startnxt = findNextStart(start,num,startnxt); finnxt = findNextFin(fin,num,finnxt); } return num[start]; } int findNextStart(int start,vector<int> &num,int preptr) { int nowNumber = num[start]; int nxtPtr = preptr == start ? start + 1 : preptr; // 若prestart正好为start，那么前进一格。否则在既有基础上出发。 while (nxtPtr < num.size() && num[start] == num[nxtPtr]) nxtPtr ++; return nxtPtr; } int findNextFin(int fin,vector<int> &num,int preptr) { int nowNumber = num[fin]; int nxtPtr = preptr == fin ? fin - 1 : preptr; while (nxtPtr >= 0 && num[fin] == num[nxtPtr]) nxtPtr --; return nxtPtr; } void swap(int *a,int *b) { int tmp = *a; *a = *b; *b = tmp; }};
【原创】leetCodeOj --- Majority Element 解题报告(脍炙人口的找n个元素数组中最少重复n/2次的元素)