数组中出现次数超过一半的数字
题目
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路
数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值：一个是数组的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。
代码（以下代码比LeetCode更加精确）
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array.length ==0 || array == null){
return 0;
}
int result = array[0];
int count =1;
for(int i =1;i<array.length;i++){
if(count == 0){
result = array[i];
count =1;
}else if(result == array[i]){
count ++;
}else{
count --;
}
}
count = 0;
for (int number : array) {
if (result == number) {
count++;
}
}
if (count > array.length / 2) {
return result;
}
return 0;
}
}
剑指offer思路2
public class Test29 {
/**
* 题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字
*
* @param numbers 输入数组
* @return 找到的数字
*/
public static int moreThanHalfNum(int[] numbers) {
// 输入校验
if (numbers == null || numbers.length < 1) {
throw new IllegalArgumentException("array length must large than 0");
}
// 用于记录出现次数大于数组一半的数
int result = numbers[0];
// 于当前记录的数不同的数的个数
int count = 1;
// 从第二个数开始向后找
for (int i = 1; i < numbers.length; i++) {
// 如果记数为0
if (count == 0) {
// 重新记录一个数，假设它是出现次数大于数组一半的
result = numbers[i];
// 记录统计值
count = 1;
}
// 如果记录的值与统计值相等，记数值增加
else if (result == numbers[i]) {
count++;
}
// 如果不相同就减少，相互抵消
else {
count--;
}
}
// 最后的result可能是出现次数大于数组一半长度的值
// 统计result的出现次数
count = 0;
for (int number : numbers) {
if (result == number) {
count++;
}
}
// 如果出现次数大于数组的一半就返回对应的值
if (count > numbers.length / 2) {
return result;
}
// 否则输入异常
else {
throw new IllegalArgumentException("invalid input");
}
}
public static void main(String[] args) {
// 存在出现次数超过数组长度一半的数字
int numbers[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
System.out.println(moreThanHalfNum(numbers));
// 出现次数超过数组长度一半的数字都出现在数组的前半部分
int numbers2[] = {2, 2, 2, 2, 2, 1, 3, 4, 5};
System.out.println(moreThanHalfNum(numbers2));
// 出现次数超过数组长度一半的数字都出现在数组的后半部分
int numbers3[] = {1, 3, 4, 5, 2, 2, 2, 2, 2};
System.out.println(moreThanHalfNum(numbers3));
// 只有一个数
int numbers4[] = {1};
System.out.println(moreThanHalfNum(numbers4));
// 输入空指针
moreThanHalfNum(null);
// 不存在出现次数超过数组长度一半的数字
int numbers5[] = {1, 2, 3, 2, 4, 2, 5, 2, 3};
moreThanHalfNum(numbers5);
}
}
剑指offer思路1
/**
* <b>快速排序</b>
* <p>在数组中找一个元素(节点)，比它小的放在节点的左边，比它大的放在节点右边。不断执行这个操作….</p>
*
* @param array
* @return
*/
static String quickSort(int[] array) {
if (array.length <= 0) {
return null;
}
quickSort(array, 0, array.length - 1);
return Arrays.toString(array);
}
/**
* 快速排序使用递归可以很好的实现，代码的逻辑结构如下。
* <p>1. 随机的获取一个用于比较的<b>中间值</b>，通常区中间的元素 <br>
* 2. 从前往后和从后往前分别查找比<b>中间值</b>大的元素和小的元素，进行交换<br>
* 3. 直到确定不存在，交换元素，则<b>中间值</b>元素的两边就能确比</p>
*
* @param array
* @param left
* @param right
*/
static void quickSort(int[] array, int left, int right) {
int i = left;
int j = right;
//支点: 可以取任意值（但通常选取位置中间）相对来说交换次数会比较小
int pivot = array[(left + right) / 2];
//左右两端进行扫描，只要两端还没有交替，就一直扫描
while (i <= j) {
//寻找直到比支点大的数
while (pivot > array[i])
i++;
//寻找直到比支点小的数
while (pivot < array[j])
j--;
//此时已经分别找到了比支点小的数(右边)、比支点大的数(左边)，它们进行交换
if (i <= j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
//上面一个while保证了第一趟排序支点的左边比支点小，支点的右边比支点大了。
//“左边”再做排序，直到左边剩下一个数(递归出口)
if (left < j)
quickSort(array, left, j);
//“右边”再做排序，直到右边剩下一个数(递归出口)
if (i < right)
quickSort(array, i, right);
}
LeetCode
1 求众数
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
代码
public static void main(String[] args) {
int[] nums = {3,2,3};
majorityElement(nums);
}
public static int majorityElement(int[] nums) {
int a = 0;
int b = 0;
for(int i = 0; i <nums.length ; i++) {
if(b ==0){
a = nums[i];
++b;
}
else if(nums[i] == a){
++b;
}else{
--b;
}
}
return a;
}
排序
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
需要一个栈，遍历数组时处理两种情况：
① 当数组元素等于栈顶元素或栈为空时入栈；
② 当元素不等于栈顶元素时则出栈。
最后的栈顶元素即为众数。
public int majorityElement(int[] nums) {
Stack<Integer> stack = new Stack<>();
for(int i:nums){
if(stack. empty()||i==stack.peek()){
stack.push(i);
}else{
stack.pop();
}
}
return stack.peek();
}
2 求众数 II
给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。
示例 1:
输入: [3,2,3]
输出: [3]
示例 2:
输入: [1,1,1,3,3,2,2,2]
输出: [1,2]
代码
class Solution {
public List<Integer> majorityElement(int[] nums) {
int n = nums.length;
List<Integer> res = new ArrayList<>();
int c1 = 0;
int c2 = 0;
Integer res1 = null;
Integer res2 = null;
for(int i : nums) {
if(c1 == 0 && c2 == 0) {
res1 = i;
c1 = 1;
}else if(c1 != 0 && c2 != 0) {
if(i == res1) {
c1++;
}else if(i == res2) {
c2++;
}else {
c1--;
c2--;
}
}else if (c1 != 0) {//意味着c2 == 0
if(i == res1) {
c1++;
}else {
res2 = i;
c2 = 1;
}
}else if(c2 != 0) {//意味着c1 == 0
if(i == res2) {
c2++;
}else {
res1 = i;
c1 = 1;
}
}
}
//验证
c1 = 0;
c2 = 0;
for(int i : nums) {
if(i == res1) {
c1++;
}else if(i == res2) {
c2++;
}
}
if(c1 > n / 3) {
res.add(res1);
}
if(c2 > n / 3) {
res.add(res2);
}
return res;
}
}
优化写法:
for(int i : nums) {
if((c1 == 0 || res1 == i) && i != res2) {
c1++;
res1 = i;
}else if(c2 == 0 || res2 == i) {
c2++;
res2 = i;
}else {
c1--;
c2--;
}
}
代码二
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<>();
if (nums == null || nums.length == 0)
return res;
//初始化：定义两个候选人及其对应的票数
int candidateA = nums[0];
int candidateB = nums[0];
int countA = 0;
int countB = 0;
//遍历数组
for (int num : nums) {
if (num == candidateA) {
countA++;//投A
continue;
}
if (num == candidateB) {
countB++;//投B
continue;
}
//此时当前值和AB都不等，检查是否有票数减为0的情况，如果为0，则更新候选人
if (countA == 0) {
candidateA = num;
countA++;
continue;
}
if (countB == 0) {
candidateB = num;
countB++;
continue;
}
//若此时两个候选人的票数都不为0，且当前元素不投AB，那么A,B对应的票数都要--;
countA--;
countB--;
}
//上一轮遍历找出了两个候选人，但是这两个候选人是否均满足票数大于N/3仍然没法确定，需要重新遍历，确定票数
countA = 0;
countB = 0;
for (int num : nums) {
if (num == candidateA)
countA++;
else if (num == candidateB)
countB++;
}
if (countA > nums.length / 3)
res.add(candidateA);
if (countB > nums.length / 3)
res.add(candidateB);
return res;
}
