面试题39：数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
解法一: 用于笔试
使用快排sort，时间复杂度为O（NlogN）,并非最优先排序，找出中间那个数; 计算中间数的出现次数，如果超过数组长度的一半，返回，否则返回0class Solution {public: int MoreThanHalfNum_Solution(vector numbers) { // 因为用到了sort，时间复杂度O(NlogN)，并非最优 if(numbers.empty()) return 0; sort(numbers.begin(),numbers.end()); // 排序，取数组中间那个数 int middle = numbers[numbers.size()/2]; int count=0; // 出现次数 for(int i=0;i numbers.size()/2) ? middle : 0; }};
解法二:
如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。class Solution {public: // 如果输入的数组没有超过一半次数的数字，返回false bool CheckMoreThanHalf(vector numbers, int number) { int times = 0; for(int i = 0; i < numbers.size(); ++i) { if(numbers[i] == number) { ++times; } } bool isMoreThanHalf = true; if(times * 2 <= numbers.size()) { isMoreThanHalf = false; } return isMoreThanHalf; } int MoreThanHalfNum_Solution(vector numbers) { int length = numbers.size(); if(length == 0) return 0; // 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1 int result = numbers[0]; int times = 1; for(int i = 1; i < length; ++i) { if(times == 0) { // 更新result的值为当前元素，并置次数为1 result = numbers[i]; times = 1; } else if(numbers[i] == result) ++times; // 相同则加1 else --times; // 不同则减1 } // 判断result是否符合条件，即出现次数大于数组长度的一半 if(!CheckMoreThanHalf(numbers, result)) result = 0; return result; }}; 面试题42：连续子数组的最大和
输入一个整形数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O（n）
class Solution {public: bool g_InvalidInput = false; int FindGreatestSumOfSubArray(vector array) { //为了区分0和无效输入，定义了一个全局变量 if(array.size() <= 0) { g_InvalidInput = true; return 0; } g_InvalidInput = false; int CurSum = 0; // 最小的负数 int GreatestSum = 0x80000000; //int GreatestSum = 0; for(int i = 0; i < array.size(); ++i) { if(CurSum <= 0) { CurSum = array[i]; } else { CurSum += array[i]; } if(CurSum > GreatestSum) GreatestSum = CurSum; } return GreatestSum; }};
面试题53：数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
class Solution {public: // 因为data是整数，不是搜索k的两个位置，而是搜索k+0.5和k-0.5 // 这两个数应该插入的位置，然后相减即可 int Search(const vector data, double num) { int start = 0; int end = data.size() - 1; while(start <= end) { int mid = start + (end - start) / 2; if(data[mid] < num) { start = mid + 1; } else if(data[mid] > num) { end = mid - 1; } } return start; } int GetNumberOfK(vector data ,int k) { return Search(data, k + 0.5) - Search(data, k - 0.5); }};
面试题53（二）：0~n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0~n-1之内。
在范围0~n-1之内的所有数字中有且只有一个数字不在该数组中，请找出这个数字解法一: 时间复杂度为O（n）
int GetMissingNumber(const int *numbers, int length){ if(numbers == nullptr || length < 0) return -1; s1 = (length + 1) * length / 2; int sum = 0; for(int i = 0; i < length; ++i) { sum += numbers[i]; } return s1 - sum;}
解法二：
int GetMissingNumber(const int *numbers, int length){ if(numbers == nullptr || length < 0) return -1; int start = 0; int end = length - 1; while(start <= end) { int mid = start + (end - start) / 2; if(numbers[mid] != mid) { if(mid == 0 || numbers[mid - 1] == mid - 1) return mid; end = mid - 1; } else start = mid + 1; } // 如果0-n-1恰好就缺失n-1呢? // 返回最后一个 if(start = length) return length; // 无效的输入，比如数组不是按要求排序的 // 或者有数字不在0~n-1范围之内 return -1;}
面试题53（三）：数组中数值和下标相等的元素
假设一个单调递增的数组里每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如：在数组{-3， -1， 1， 3， 5}，数字3和它的下标相等
// 标准的二分查找法 int GetNumberSameAsIndex(const int* number, int length){ if(number == nullptr || length < 0) return -1; int start = 0; int end = length - 1; while(start <= end) { int mid = start + (end - start) / 2; if(number[mid] == mid) return mid; else if(number[mid] > mid) end = mid - 1; else start = mid + 1; } return -1;}