数组中出现次数超过一半的数字

题目

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为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)。