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;
}
}