[剑指Offer]-数组中出现次数超过一半的数字

题目描述

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

解题思路

当我们遍历到下一个数字的时候，如果下一个数字和当前我们保存的数字相同，则次数加 1；如果和当前我们保存的数字不同，则次数减 1；当次数减到 0 的时候，我们将保存的数字改为当前遍历所处的位置，并将次数更改为 1。时间复杂度O（n）

算法图解

参考代码：

package offer; /** * 数组中出现次数超过一半的数字 * 数组中一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为 9 的数组{1,2,3,2,2,2,5,4,2}。由于数字 2 在数组中出现了 5 次，超过数组长度的一半，因此输出 2. */ public class Offer39 { public static void main(String[] args) { int nums[] = {1, 2, 3, 2, 2, 2, 5, 4, 2}; System.out.println(findMoreHalf(nums)); } /** * O(n) * @param nums * @return */ static int findMoreHalf(int nums[]) { if (nums == null || nums.length <= 1) { return 0; } int tag = 1; int result=nums[0]; for (int i = 0; i < nums.length - 1; i++) { int curent = nums[i]; if (tag == 0) { result= nums[i]; tag = 1; } if (curent == nums[i + 1]) { tag++; } else { tag--; } } return result; } }

题目描述（最小K个数）

输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

解题思路

排序后输出。时间复杂度O（nlogn）

算法图解

参考代码：

package offer; import java.util.Arrays; /** * 最小的K个数 * 输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 */ public class Offer40 { public static void main(String[] args) { int nums[] = {4, 5, 1, 6, 2, 7, 3, 8}; int k = 5; /** * 排序后找 */ Arrays.sort(nums); for (int i = 0; i < k; i++) { System.out.println(nums[i]); } } }

---

附录

该题源码在我的 ?Github 上面！