第一题：数组中出现次数超过一半的数字
仔细分析一下，这个数字必定是数组的中位数。可以利用快排的思想
int MoreThanHalfNum(vector<int> &nums) { int length = nums.size(); int middle = length >> 1; int start = 0; int end = length - 1; int index = Partition(nums, start, end); while (index != middle) { if (index > middle) { end = index - 1; index = Partition(nums, start, end); } else { start = index + 1; index = Partition(nums, start, end); } } return nums[index]; }或者还有一个更好的算法，如果数组中一个数字出现次数超过一半，那么就是说它出现的次数比所有数字出现次数和还要多。因此我们可以在遍历数组的时候保存两个值：值与次数，遇到相同次数加1，否则减1，如果次数为0，则放弃当前，保存下一个。 int MoreThanHalfNum(vector<int> &nums) { int value = nums[0]; int count = 1; for (int i = 1; i < nums.size(); i++) { if (nums[i] == value) ++count; else --count; if (count == 0) { value = nums[i]; count = 1; } } return value; } 第二题：最小的k个数这一题同样可以用快排思想来解，如果基于数组的第k个数字来调整，使得比第k个数字小的都在数组的左边。和上面一题同样解法，只不过把middle 换成k-1
另一种解法是用容器保存最小的k个数，如果已有的数据小于k个，则执行插入操作。如果已经有k个数，则执行替换操作。
void GetLeastNumbers(vector<int> &nums, int k) { multiset<int, greater<int> > leastNums; for (int i = 0; i < nums.size(); i++) { if (leastNums.size() < k) leastNums.insert(nums[i]); else { multiset<int, greater<int> >::iterator it = leastNums.begin(); if (nums[i] < *it) { leastNums.erase(it); leastNums.insert(nums[i]); } } } multiset<int, greater<int> >::iterator begin = leastNums.begin(); multiset<int, greater<int> >::iterator end = leastNums.end(); while (begin != end) { cout << *begin; begin++; } cout << endl; } 第三题：连续子数组最大和这一题leetcode上也有，记住当前sum与历史sum，如果当前sum小于0，那么重置当前sum为当前数，否则进行相加操作。如果当前sum大于历史sum，则赋值。
int FindGreatestSumOfSubArray(vector<int> &nums) { int cSum = 0; int GreatestSum = INT_MIN; for (int i = 0; i < nums.size(); i++) { if (cSum < 0) cSum = nums[i]; else cSum += nums[i]; if (cSum > GreatestSum) GreatestSum = cSum; } return GreatestSum; }第四题：从1到n整数中1出现的次数
从1到n整数中1出现的次数 这个博客的解法比书上要好的多。
第五题：把数组排成最小的数
书上的解法是将数字转换为字符串，然后定义排序规则，即AB与BA的大小进行比较来排序A和B，关键在于字符串一些函数的运用，比如sprintf函数,strcpy、strcat、strcmp函数
第六题：丑数，我们把只包含因子2、3和5的数称为丑数，求按小到大的顺序第1500个丑数
如何判断一个数是否为丑数：如果一个数能被2整除，我们就把它连续除以2，如果能被3整除，就连续除以3，如果能被5整除，连续除以5，最后如果是1，则为丑数否则不是。
bool IsUgly(int number) { while (number % 2 == 0) number /= 2; while (number % 3 == 0) number /= 3; while (number % 5 == 0) number /= 5; return (number == 1) ? true : false; }基于这个判断，我们可以按照顺序判断每一个数是否为丑数，时间复杂度不够好。我们考虑一个数组，数组存储的是当前的丑数，以后的每个丑数，都是用之前的数组的元素相乘的来的。接下来就是如何得到后面的丑数并保证它是有序的。可以想到，数组的第一个元素是1,1与2 3 5分别相乘，可以得到三个值，这三个值里面最小的，肯定就是下一个丑数的最大值，接着max2的下标后移，继续比较。
void mkUglyNumber(){ gArr[top++] = 1; int *max2 = gArr; int *max3 = gArr; int *max5 = gArr; while(top < 1500){ int min = getMin(*max2*2,*max3*3,*max5*5); gArr[top] = min; while(*max2*2 <= gArr[top]) ++max2; while(*max3*3 <= gArr[top]) ++max3; while(*max5*5 <= gArr[top]) ++max5; ++top; } } 第七题：第一个只出现一次的字符
由于字符可与整数进行互换，且字符最多为256个，所以可以用一个大小为256的数组来记录字符出现的次数。此题较为简单。
第八题：数组中的逆序对
在数组中的两个数字如果前面一个数字大于后面的数字，则成为逆序对。此题可以利用归并排序来解，此博客比较详细 点击打开链接
第九题：两个链表的第一个公共结点
第一种方法是用栈来解决，先将两个链表分别入栈，然后逐一出栈比较，最后一个相同的即为第一个公共结点
第二种方法是先遍历两个链表，得到长度为m和n，先在长的链表上走m-n（假设m>n），再一起走，第一个相同的即为所求点
第三种可以用带环链表求解，因为两个链表相交，必定为Y型，可以变成带环链表
