面試 19：輸出數(shù)組中出現(xiàn)次數(shù)超過一半的數(shù)字（劍指 Offer 26 題）
上一篇推文給大家留下的習(xí)題來自于《劍指 Offer》第 29 題：數(shù)組中超過一半的數(shù)字，不知道各位去思考了么？
面試題：數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，請找出這個數(shù)字并輸出。比如 {1,2,3,2,2,2,1} 中 2 的次數(shù)是 4，數(shù)組長度為 7，所以輸出 2。要求不能修改輸入的數(shù)組。
準備測試用例
這道題能思考到的測試用例比較簡單。
- 輸入符合條件的數(shù)組，查看打印是否滿足情況；
- 輸入不符合條件的數(shù)組，查看打??；
- 輸入只有一個元素的數(shù)組，查看打??；
- 輸入無效數(shù)組，查看打??；
思考程序邏輯
第二步便是我們的思考程序邏輯了，題目要求查找出現(xiàn)次數(shù)超過一半的數(shù)字。比較容易想到的思路是直接對數(shù)組排序，那中間那個值就是我們想要的值，但這樣的想法明顯排序后會對輸入的數(shù)組順序有影響，所以我們可能需要換一種思路。
再看一遍題干，我們不難思考到，我們是否可以對每個數(shù)字進行計數(shù)，最后返回計數(shù)次數(shù)最多的值。存儲次數(shù)采用 map 做映射處理。
public class Test19 {
private static int moreThanHalfNums(int[] nums) {
if (nums == null || nums.length == 0)
throw new RuntimeException("the length of array must be large than 0");
int len = nums.length;
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
if (map.containsKey(num))
map.put(num, map.get(num) + 1);
else
map.put(num, 1);
}
int times = len / 2;
// 查找 map 中 value 最大的值
for (Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() > times)
return entry.getKey();
}
throw new RuntimeException("invalid input!");
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 3, 2, 2, 4, 2, 2, 5};
System.out.println(moreThanHalfNums(nums1));
int[] nums2 = {1};
System.out.println(moreThanHalfNums(nums2));
int[] nums3 = {2, 1, 2, 1, 2, 2, 3, 2, 1};
System.out.println(moreThanHalfNums(nums3));
int[] nums4 = {1, 2, 3, 4, 5};
System.out.println(moreThanHalfNums(nums4));
}
}
寫畢后進行測試用例的驗證，無不例外，目前都通過，于是我們把這樣的代碼解法遞交給面試官。
面試官看了這樣的算法，表示他更期待的是不使用任何輔存空間的算法。于是我們得換個角度思考。
數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半，也就是說它出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)次數(shù)的和還要多。因此我們可以考慮在遍歷數(shù)組的時候保存兩個值： 一個是數(shù)組中的一個數(shù)字， 一個是次數(shù)。當(dāng)我們遍歷到下一個數(shù)字的時候，如果下一個數(shù)字和我們之前保存的數(shù)字相同，則次數(shù)加 1 ；如果下一個數(shù)字和我們之前保存的數(shù)不同，則次數(shù)減 1。如果次數(shù)為 0，我們需要保存下一個數(shù)字，并把次數(shù)設(shè)為 1 。由于我們要找的數(shù)字出現(xiàn)的次數(shù)比其他所有數(shù)字出現(xiàn)的次數(shù)之和還要多，那么要找的數(shù)字肯定是最后一次把次數(shù)設(shè)為 1 時對應(yīng)的數(shù)字。
我們來看這樣的思路用代碼怎么實現(xiàn)。
public class Test19 {
private static int moreThanHalfNums(int[] nums) {
if (nums == null || nums.length == 0)
throw new RuntimeException("the length of array must be large than 0");
int result = nums[0];
int times = 1;
int len = nums.length;
for (int i = 1; i < len; i++) {
if (times == 0) {
result = nums[i];
times = 1;
} else if (result == nums[i])
times++;
else
times--;
}
times = 0;
for (int num : nums) {
if (num == result)
times++;
}
if (times > len / 2)
return result;
throw new RuntimeException("invalid input!");
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 3, 2, 2, 4, 2, 2, 5};
System.out.println(moreThanHalfNums(nums1));
int[] nums2 = {1};
System.out.println(moreThanHalfNums(nums2));
int[] nums3 = {2, 1, 2, 1, 2, 2, 3, 2, 1};
System.out.println(moreThanHalfNums(nums3));
int[] nums4 = {1, 2, 3, 4, 5};
System.out.println(moreThanHalfNums(nums4));
}
}
寫畢后，驗證測試用例，同樣全部通過。
本題最后的思路，希望大家刻意去思考和記憶一下，因為也許變一下題意，這樣的想法還可以用到。
課后習(xí)題
我們下一次推文的題目來源于《劍指 Offer》第 31 題：計算連續(xù)子數(shù)組的最大和。
面試題：輸入一個整型數(shù)組，數(shù)組中有正數(shù)也有負數(shù)。數(shù)組中一個或多個整數(shù)形成一個子數(shù)組，求所有子數(shù)組的和的最大值，要求時間復(fù)雜度為 O(n)。
比如輸入 {1, -2, 3, 10, -4, 7, 2, -5}，能產(chǎn)生子數(shù)組最大和的子數(shù)組為 {3,10,-4,7,2}，最大和為 18。
