JZ28 数组中出现次数超过一半的数字
（简单）
题目
描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。你可以假设数组是非空的，并且给定的数组总是存在多数元素。1<=数组长度<=50000
示例1
输入：
[1,2,3,2,2,2,5,4,2]
返回值：
2
示例2
输入：
[3,3,3,3,2,2,2]
返回值：
3
示例3
输入：
[1]
返回值：
1
思路
此题用排序取中值的思路即可解出，因为一个数在数组中出现的次数超过一半，那么将这个数组进行有序排序后，此数势必出现在中间，因此，这道题目也就成了一道考察排序算法的题目，因此，我们选择合适的排序算法即可。
（补充：关于七大排序算法的用法，代码实现，思路，可参考之前文章：Java实现七种【排序算法】+图解+完整代码+分析）
由于选择排序算法适合处理序列基本有序时的情况，而此题的序列因为有一半以上相同的值，而且题目已给定说明测试序列的长度（1<=数组长度<=50000），因此，符合基本有序的情况，我们可以用此算法来测试
public int MoreThanHalfNum_Solution(int [] array) {
sort(array);
return array[(array.length - 1) / 2];
}
public static void sort(int[] a) {
int i, j;
int n = a.length - 1;
int min;
for (i = 0; i < n; i++) {
min = i;
for (j = i + 1; j <= n; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if (i != min) {
swap(a, i, min);
}
}
}
private static void swap(int[] a, int x, int y) {
int temp;
temp = a[x];
a[x] = a[y];
a[y] = temp;
} 但发现其效率特别低：
我们接下来用冒泡排序测试，由于冒泡排序适合处理和选择排序的思路都有交换排序的影子，因此也适用于此基本有序的数组序列的处理，我们来进行测试
public int MoreThanHalfNum_Solution(int[] array) {
sort(array);
return array[(array.length - 1) / 2];
}
public static void sort(int[] array) {
int i, j;
int len = array.length - 1;
boolean flag = true;
for (i = 0; i < len && flag; i++) {
flag = false;
for (j = len - 1; j >= i; j--) {
if (array[j] > array[j + 1]) {
swap(array, j, j + 1);
flag = true;
}
}
}
}
private static void swap(int[] a, int x, int y) {
int temp;
temp = a[x];
a[x] = a[y];
a[y] = temp;
} 算法效率稍微有所提高，但仍然达不到高效的要求：
接下来，我们用优化版的快速排序来测试
public static int MoreThanHalfNum_Solution(int [] array) {
sort(array);
return array[(array.length - 1) / 2];
}
public static void sort(int[] a) {
int n = a.length - 1;
QSort(a, 0, n);
}
private static void QSort(int[] a, int low, int high) {
int ORDINARY_LEN = 7; // 数组长度阈值，当小于时，可用直接插入排序
int pivot; // 枢轴的下标，将某个数放在此位置，使得它左边的值都比它小，右边的都比它大
if ((high - low) > ORDINARY_LEN) {
while (low < high) {
pivot = Partition(a, low, high); // 将a[low..high]一分为二，算出枢轴下标pivot
QSort(a, low, pivot - 1); // 对低子表递归排序
low = pivot + 1; // 尾递归
}
} else {
interSort(a);
}
}
// 交换顺序表a中子表的记录，使枢轴记录到为，并返回其位置
private static int Partition(int[] a, int low, int high) {
int pivotkey;
int m = low + (high - low) / 2;
if (a[low] > a[high]) {
swap(a, low, high);
}
if (a[m] > a[high]) {
swap(a, high, m);
}
if (a[m] > a[low]) {
swap(a, m, low);
}
pivotkey = a[low]; // 此时a[low]为三数取中得到的中间值
int temp = pivotkey; // 哨兵
while (low < high) { // 从表的两端交替向中间扫描
while (low < high && a[high] >= pivotkey) {
high--;
}
a[low] = a[high]; //改交换为替换
while (low < high && a[low] <= pivotkey) {
low++;
}
a[high] = a[low];
}
a[low] = temp;
return low; // 最终low == high，所有返回枢轴所在位置
}
private static void swap(int[] a, int x, int y) {
int temp;
temp = a[x];
a[x] = a[y];
a[y] = temp;
}
public static void interSort(int[] a) {
int i, j;
int n = a.length - 1;
for (i = 0; i < n; i++) {
int temp = 0;
if (a[i] > a[i + 1]) {
temp = a[i + 1]; // 设置哨兵
for (j = i; a[j] > temp && j > 0; j--) {
a[j + 1] = a[j];
}
a[j + 1] = temp;
}
}
} 效率更低了。。
用哈希法，用map存储每个键值的出现次数，存完检查为众数直接返回该数，循环结束直接返回0，测试一下效果如何
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
Map<Integer,Integer> map = new HashMap();
for(int e : array) {
// 记录e出现次数
if(map.containsKey(e)) {
map.put(e,map.get(e) + 1);
} else {
map.put(e, 1);
}
// 超过一半则直接返回
if(map.get(e) > array.length / 2) {
return e;
}
};
return 0;
}
} 最终，经过测试，针对此题，候选法（最优解） 是最高效的，此处参考的是一位提交 Java 代码的大佬的思路（链接：https://blog.nowcoder.net/n/f5a58cf0facf4cfb92bb971706b69ebd）
加入数组中存在众数，那么众数一定大于数组的长度的一半。
思想就是：如果两个数不相等，就消去这两个数，最坏情况下，每次消去一个众数和一个非众数，那么如果存在众数，最后留下的数肯定是众数。
具体做法：
- 若一定存在一个众数：遍历数组，每到一个元素会经历一次投票，如果目前候选人为自己，票+1，否则票-1，由于众数出现次数超过其他所有数，所以即使其他人全投的众数反对票，众数也能当任，即最后剩下的候选人为众数
- 若不一定存在众数：候选人法可能出现问题，则再遍历一边查看是否为众数即可
实现
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
int people = 0, tickets = 0;
// 轮流投票
for(int e : array) {
// 新人上任
if(tickets == 0) {
people = e;
}
// 支持自己，反对别人
if(people == e) {
tickets++;
} else {
tickets--;
}
}
// 检测该数是否为众数
tickets = 0;
for(int e : array) {
if(e == people && ++tickets > array.length / 2) {
return people;
}
}
return 0;
}
} JZ34 第一个只出现一次的字符
（简单）
题目
描述
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
示例
输入：
“google”
返回值：
4
思路
实现
public class Solution {
public int FirstNotRepeatingChar(String str) {
if (str == null || str.length() == 0) {
return -1;
}
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
boolean flag = true;
for (int j = 0; j < chars.length; j++) {
if (i == j) {
continue;
}
if (chars[i] == chars[j]) {
flag = false;
break;
}
}
if (flag) {
return i;
}
}
return -1;
}
}