几道常见算法面试题
本文由玉刚说写作平台提供写作赞助，版权归玉刚说微信公众号所有。
原作者：Jiantao
版权声明：未经玉刚说许可，不得以任何形式转载。
数据结构和算法有多重要？
我想有追求的程序员都不会放过它的。 打个比方，在金庸的武侠世界里，数据结构和算法它就像一门上乘的内功心法，一旦掌握了它，各种武功信手拈来，毫无压力（张无忌就是一个典型的例子）；对于程序员来说，它能决定你在技术这条道路上能走多远。
本文主要涉及数组、字符串、List这几个数据结构，然后通过解答和分析几道常见的面试题，从中分享一些我的学习心得和解题套路，希望对你有帮助。
题目1：翻转句子
题目： 给定一个英文句子，每个单词之间都是由一个或多个空格隔开，请翻转句子中的单词顺序（包括空格的顺序），但单词内字符的顺序保持不变。例如输入"www google com "，则应输出" com google www"。
如果你经常关注算法相关文章，这道题应该会比较熟悉，各种博客和书籍上都有出现，不熟悉也没关系，现在我们就一起来尝试解答下。这里要注意题意和网上流传的题目有个不同点：网上基本都是单词间有且只有一个空格。而此题需要考虑一个或多个空格的情况。
解题思路
试想一下，如果将整个字符串翻转，结果是句子是反转了，但单词内的字符顺序也翻转了。如果要保证单词内顺序不变，只需要再将每个单词翻转一下就满足要求了。
由于题中“www google com ”字符串较长，我就以" hello world"为例分析下这个过程，请看下图。
yugang-v1-0-solution.png
图 1.0 翻转句子，但保证句子中单词内部字符顺序。
注：（1）字符串" hello world"初始状态，注意首字符是空格。 （2）将" hello world"整个句子翻转后的样子。可以看出不仅翻转了句子中单词的顺序(包括空格)，连单词内的字符顺序也翻转了。(3) 定义两个指针p1、p2都指向句子的首字符。 （4）首字符d，不是空格，此时p1指针不动，p2指针向右移动1位，指向字符 l。（移动p2指针目的：检查单词的结束位置。） （5）由于第二个字符为 l ，也不是空格，p2继续向右移动1位。（6）多次移动后，p2指针在第一个空格处停下来，此时就能得知p2-1为该单词的结束位置。（7）反转两个指针（p1、p2-1）中间的字符串。（8）交换后，重置两个指针位置p1=p2++。以此类推，继续寻找下一个单词并翻转，直到指针移动到句子末尾就结束循环。
此思路的关键是：1. 实现一个函数/方法，翻转字符串中的一段。 2. 判断并获取句子中的单词，注意空格。
测试用例
- 功能测试：多个单词、1个单词、单词间只有一个空格、单词间有多个空格。
- 特殊输入测试：空字符、字符串中只有空格、null对象（指针）。
编码实现
- Java代码
/**
* @param chars 原字符串
* @param start 大于等于0
* @param end 小于 length
* @return
*/
private char[] v1_0_reverse(char[] chars, int start, int end) {
// str 判断null， 索引有效值判断
if (chars == null || start < 0 || end >= chars.length || start >= end) {
return chars;
}
while (start < end) {
// 收尾字符互换，直到替换完成。
char temp = chars[start];
chars[start] = chars[end];
chars[end] = temp;
start++;
end--;
}
return chars;
}
private String v1_0_solution(String sentence) {
if (sentence == null || sentence.isEmpty()) {
return sentence;
}
int length = sentence.length();
// 第一步翻转所有字符
char[] chars = v1_0_reverse(sentence.toCharArray(), 0, length - 1);
System.out.println(new String(chars));
// 第二步翻转每个单词（重点：怎么找到单词）
int start = 0, end = 0;
while (start < length) {
if (chars[start] == ' ') {
// 遇到空格就向右边继续查找
start++;
end++;
} else if (end == length || chars[end] == ' ') {
// 遇到空格或者已经到了字符串末尾，此时翻转找到的单词内部字符，这里需要注意end-1
chars = v1_0_reverse(chars, start, end - 1);
System.out.println(new String(chars));
// 重新制定检查索引start
start = end++;
} else {
// end加1，为了检查单词是否结束
end++;
}
}
return new String(chars);
}
- C++ 代码实现
// 反转字符串
void Reverse(char *pBegin, char *pEnd)
{
if(pBegin == NULL || pEnd == NULL)
return;
while(pBegin < pEnd)
{
char temp = *pBegin;
*pBegin = *pEnd;
*pEnd = temp;
pBegin ++, pEnd --;
}
}
// 翻转句子中单词顺序，但保证单词内字符顺序不变。
char* ReverseSentence(char *pData)
{
if(pData == NULL)
return NULL;
char *pBegin = pData;
char *pEnd = pData;
while(*pEnd != '\0')
pEnd ++;
pEnd--;
// 翻转整个句子
Reverse(pBegin, pEnd);
// 翻转句子中的每个单词
pBegin = pEnd = pData;
while(*pBegin != '\0')
{
if(*pBegin == ' ')
{
pBegin ++;
pEnd ++;
}
else if(*pEnd == ' ' || *pEnd == '\0')
{
Reverse(pBegin, --pEnd);
pBegin = ++pEnd;
}
else
{
pEnd ++;
}
}
return pData;
}
如果你在面试的时候遇到这道题，并且很容易就想到了这个算法，有经验的面试官就会在这道题基础上加点难度，继续考查面试者。so，第二道题来了：
题目：接上题，面试官继续提问，我们得到的" com google www"需要被用作一个URL的参数，所以这里需要的处理是去掉开头结尾的无效空格，并将两个单词中间的每一个空格都替换为"%20"。例如" com google www"应被转换为"com%20%20google%20www"，请给出转换函数。
解题思路
- 第一步去掉收尾的无效空格；比如" com google www"去掉后得到"com google www"。
- 第二步将两个单词中间的每一个空格都替换为"%20"。
还是以" hello world"为例，简单分析下解题过程，请看下图。
反转字符串02.png
图 1.1 剔除收尾无效空格，并将单词间的每一个空格都替换为"%20"。
注：（1）字符串" hello world"，这里注意首字符是空格。 （2）剔除首尾空格后。 （3）对原字符串进行扩容。newLen = len + 2 x blackCount；这里解释下新数组的长度是如何计算的，由于是将每一个空格都替换为"%20",就相当于原来占一个字符替换后要占三个字符，换言之，每一个空格就会多出两个字符长度，所以就有前面的表达式。 （4） 定义两个指针p1、p2，分别指向len-1和newLen-1位置。 （5）判断p1指针是否指向空格，如果是则在p2处开始插入字符“%20”，不是则将p1指向的值复制给p2并将两个指针往左移动一位。这里将p1指向的字符 d 赋值给p2，并将两个指针向左移动一位。 （6）将p1指向的字符 l 赋值给p2，并移动指针。 （7）多次赋值和移动后，p1指向了第一个空格。 （8）在p2处依次插入字符 0 、 2 、 % ，并指针p2向左移动三位，结束后将p1向左移动一位，此时p1、p2重合结束循环。
测试用例
- 功能测试：前后有无空格情况、中间一个或多个空格情况。
- 特殊输入测试：空字符、字符串中只有空格、null对象（指针）。
编码实现
- Java代码
private String v1_1_solution(String sentence) {
if (sentence == null || sentence.isEmpty()) {
return sentence;
}
// 去掉字符串收尾的空格
sentence = trim(sentence);
int len = sentence.length();
char[] chars = sentence.toCharArray();
int count = getSpaceCount(sentence);
int newLen = 2 * count + len;
// 扩容，内部使用System.arraycopy 方法实现。
chars = Arrays.copyOf(chars, newLen);
int index = len - 1;
int newIndex = newLen - 1;
while (index >= 0 && newIndex > index) {
if (chars[index] == ' ') {
chars[newIndex--] = '0';
chars[newIndex--] = '2';
chars[newIndex--] = '%';
} else {
chars[newIndex--] = chars[index];
}
index--;
}
return new String(chars);
}
/**
* 剔除字符串收尾的空格
*
* @param origin
* @return
*/
private String trim(String origin) {
char[] chars = origin.toCharArray();
int length = chars.length;
int st = 0;
while (st < length && chars[st] == ' ') {
st++;
}
while (st < length && chars[length - 1] == ' ') {
length--;
}
// 如果收尾有空格，就截取生成新的字符串
if (st > 0 || length < chars.length) {
origin = new String(chars, st, (length - st));
}
return origin;
}
private int getSpaceCount(String sentence) {
char[] chars = sentence.toCharArray();
int count = 0;
for (char c : chars) {
if (c == ' ') {
count++;
}
}
return count;
}
- C++实现
/* 去掉收尾空格:将原字符串截取后返回新字符串 */
void trim(char *strIn, char *strOut){
int i = 0;
int j = strlen(strIn) - 1;
while(strIn[i] == ' ')
++i;
while(strIn[j] == ' ')
--j;
strncpy(strOut, strIn + i , j - i + 1);
strOut[j - i + 1] = '\0';
}
/*length 为字符数组string的总容量*/
void replaceBlank(char string[], int length)
{
if(string == NULL && length <= 0)
return;
/*originalLength 为字符串string的实际长度*/
int originalLength = 0;
int numberOfBlank = 0;
int i = 0;
while(string[i] != '\0')
{
++ originalLength;
if(string[i] == ' ')
++ numberOfBlank;
++ i;
}
/*newLength 为把空格替换成'%20'之后的长度*/
int newLength = originalLength + numberOfBlank * 2;
if(newLength > length)
return;
int indexOfOriginal = originalLength;
int indexOfNew = newLength;
while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal)
{
if(string[indexOfOriginal] == ' ')
{
string[indexOfNew --] = '0';
string[indexOfNew --] = '2';
string[indexOfNew --] = '%';
}
else
{
string[indexOfNew --] = string[indexOfOriginal];
}
-- indexOfOriginal;
}
}
题目2：调整数组中元素顺序
题目： 给定一个整数数组，请实现一个函数来调整数组中数字的顺序，使得所有奇数都位于偶数之前。
解题思路
此题比较简单，我最先想到的解法是这样：我们维护两个指针(索引)，一个指针指向数组的第一个数字，称之为头指针，向右移动；一个指针指向最后一个数字，称之为尾指针，向左移动。
yugang-dsaa-v2.0.png
图2.0 调整数组{2，1，3，6，4，7，8，5}使得奇数位于偶数前面的过程。
注：（1）初始化两个指针P1、P2，分别指向数组的头部和尾部。（2）由上一步得知，指针P1指向的数字是偶数2，而P2指向的数字是奇数5，满足条件，我们交换这两个数字。（3） P1继续向右移动直到指向偶数6，P2继续向左移动直到指向奇数7。（4）交换两个指针指向的数字。（5）P1，P2继续移动后重叠，表明所有奇数已位于偶数前面了。
循环结束条件：两个指针重叠时或P2指针移动到了P1指针的前面，此时退出循环。
可以看出此算法，一次循环搞定，所以时间复杂度O(n), 由于在原数组上操作，所以空间复杂度O(1)。
测试用例
- 功能测试：全是奇数、全是偶数、奇偶数存在但已排好序/未排好序。
- 特殊输入测试： null对象、数组元素为0、有负数情况。
编码
- Java实现
private int[] v2_0_solution(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int st = 0;
int end = nums.length - 1;
while (st < end) {
// find even number
if (isOdd(nums[st])) {
st++;// 奇数，索引右移
} else if (!isOdd(nums[end])) {
end--;// 偶数，索引左移
} else {
// 奇偶数互换
int temp = nums[st];
nums[st] = nums[end];
nums[end] = temp;
st++;
end--;
}
}
return nums;
}
// 与1做按位运算，不为0就是奇数，反之为偶数
private boolean isOdd(int n) {
return (n & 1) != 0;
}
- C++实现
// 互换
void swap(int* num1, int* num2)
{
int temp = *num1;
*num1 = *num2;
*num2 = temp;
}
//判断是否为奇数
bool isOdd(int data)
{
return (data & 1) != 0;
}
//奇偶互换
void oddEvenSort(int *pData, unsigned int length)
{
if (pData == NULL || length == 0)
return;
int *pBegin = pData;
int *pEnd = pData + length - 1;
while (pBegin < pEnd)
{
//如果pBegin指针指向的是奇数，正常，向右移
if (isOdd(*pBegin))
{
pBegin++;
}
//如果pEnd指针指向的是偶数，正常，向左移
else if (!isOdd(*pEnd))
{
pEnd--;
}
else
{
//否则都不正常，交换
swap(pBegin, pEnd);
}
}
}
有经验的面试官又来了，题目难度需要升下级，😶~
题目： 接上题，面试官会继续要求改造此函数使其能够保证原先输入数组的奇数内部顺序以及偶数内部顺序，即如果输入为{2，1，3，6，4，7，8，5}，则输出应为{1，3，7，5，2，6，4，8}，奇数之间的相互顺序和偶数之间的相互顺序不得被改变。
解题思路
要想保证原数组内元素的顺序，可使用O(n)的temp数组空间按顺序缓存偶数，奇数依次放到原数组前面，最后将temp中偶数取出放在原数组后面。
yugang-dsaa-v2-1.png
图 2.1 借助O(n)的temp数组缓存偶数，进而保证原数组顺序。
注： 变量解释：st为即将插入的奇数在原数组中的索引，evenCount为缓存的偶数个数。（1）初始化和原数组相同长度的数组temp，指针p1指向首个元素，st=eventCount=0。 （2）将p1指向的偶数 2 放入在temp中，evenCount自加1。 （3）由于p1指针向右移动一位指向的是奇数 1 ，所以将p1指向的值赋值给Array[st]，此时还st=0，赋值完成后st自加1。 （8）依次逻辑，直到循环结束时，已完成原数组中奇数元素按顺序插入到了头部，偶数按顺序缓存在了temp数组中，即图中状态。
上图展示了偶数按顺序缓存到temp数组中，奇数按顺序放到原数组前面。最后将temp数组中的偶数依次按序放在原数组后面，这个过程较简单，就没体现到图中，具体请看下面代码实现。
测试用例
同上一题。这里就省略了。
编码
- Java实现
private int[] v2_1_solution(int[] nums) {
if (nums == null || nums.length <= 1) {
return nums;
}
int st = 0;
int evenCount = 0;
int[] temp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
if (!isOdd(nums[i])) {
evenCount += 1;
temp[evenCount - 1] = nums[i];
} else {
if (st < i) {
// 将奇数依次放在原数组前面
nums[st] = nums[i];
}
st++;
}
}
if (evenCount > 0) {
for (int i = st; i < nums.length; i++) {
nums[i] = temp[i - st];
}
}
return nums;
}
- C++实现
void v2_1_solution(int* nums,unsigned int len)
{
if (!nums || len <= 1) {
return;
}
int st = 0;
int evenCount = 0;
// 申请的内存空间temp
int temp[len];
for (int i = 0; i < len; i++) {
if (!isOdd(nums[i])) {
evenCount += 1;
temp[evenCount - 1] = nums[i];
} else {
if (st < i) {
// 将奇数依次放在原数组前面
nums[st] = nums[i];
}
st++;
}
}
// 将temp中偶数取出放在原数组后面
if (evenCount > 0) {
for (int i = st; i < len; i++) {
nums[i] = temp[i - st];
}
}
}
题目3：利用数组实现一个简易版的List
题目：请利用数组实现一个简易版的List，需要实现poll和push两个接口，前者为移除并获得队头元素，后者为向队尾添加一个元素，并要求能够自动扩容。
解题思路
还是以“hello world”为例，作图分析下。
用数组实现List.png
图 3.0 List的push和poll过程
注：（1） 初始化List，数组默认容量len为8，size=0。（容量小一点方便作图，实际容量看需求而定。） （2） 队尾添加字符 h ，size++。 （3）添加len-1个字符后，size指向数组最后一个位置。 （4）如果再添加字符 O ，由于size++满足条件：大于等于len，此时需要先对List先扩容，扩容后，再进行添加字符操作。 （5） 接着继续添加，直到“hello world”都push到List中。 （6）这是一个poll过程，可以看出即获取了对头元素 h ，并且整个数组中元素向左移动一位来实现移除效果。
关于扩容：每次扩容多少？上图例子是变为原来的2倍。像ArrayList则是这样 int newCapacity = oldCapacity + (oldCapacity >> 1)，可以看出扩容后大小 = 原来大小 + 原来大小/2。所以扩容多少由你自己决定。
此题关键是在怎么实现poll和push两个接口上。
- push（添加元素）：按索引添加到数组中，size大于等于数组长度时就先扩容。
- poll（获取并移动对头元素）：移动数组并置空最后一个元素。
测试用例
- 功能测试： 添加、移除元素
- 特殊测试： 添加大量数据（测试扩容）、移除所有元素、null数据
编码
- Java实现
private static final int DEFAULT_CAPACITY = 16;
private Object[] elementData;
// 实际存储的元素数量
// The size of the List (the number of elements it contains).
private int size;
public CustomList() {
elementData = new Object[DEFAULT_CAPACITY];
}
public CustomList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = new Object[DEFAULT_CAPACITY];
} else {
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
}
}
/**
* 移除并获得队头元素
*
* @return
*/
public Object poll() {
if (size <= 0){
throw new IndexOutOfBoundsException(" list is empty .");
}
// 获取队头第一个元素
Object oldValue = elementData[0];
// 数组元素左移一位 & 最后一位元素置空
System.arraycopy(elementData, 1, elementData, 0, size - 1);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* 向队尾添加一个元素
*
* @param item
*/
public void push(Object item) {
ensureExplicitCapacity(size + 1); // Increments modCount!!
elementData[size++] = item;
}
@Override
public String toString() {
return Arrays.toString(elementData);
}
// 这里扩容参考的ArrayList，具体实现请点击文末源代码链接前往查看。
private void ensureExplicitCapacity(int minCapacity) {
// 期望的最小容量大于等于现有数组的长度，则进行扩容
if (minCapacity - elementData.length >= 0)
grow(minCapacity);
}
- C++实现
class List {
private:
int expansionSize = 16;//每次扩容个数
int elemsSize = 0;//数组长度
int dataIndex = -1;//最后一位元素下标
T* elems; //元素
public:
List(){
elemsSize = 0;
dataIndex = -1;
}
List(int initialCapacity){
if (initialCapacity<=0) {
throw out_of_range("initialCapacity must > 0");
}
elemsSize = initialCapacity;
elems = new T[initialCapacity];
}
void push(T const&); // 入栈
T poll(); // 出栈
int size();
~List(){
if(elemsSize>0){
delete []elems;
}
}
};
template <class T>
void List<T>::push (T const& elem)
{
if(elemsSize <= 0){//初始化数组
elemsSize = expansionSize;
elems = new T[elemsSize];
}
if(dataIndex+1 >= elemsSize){//数组扩容
elemsSize += expansionSize;
T* newElems = new T[elemsSize];
for(int i=0;i<=dataIndex;i++){
newElems[i] = elems[i];
}
delete[]elems;
elems = newElems;
}
dataIndex++;
elems[dataIndex] = elem;
}
template <class T>
T List<T>::poll ()
{
if (dataIndex<0) {
throw out_of_range("List<>::poll(): empty List");
}
T poll = elems[0]; //获取第一位
for(int i=1;i<=dataIndex;i++){//后面元素向左移
elems[i-1] = elems[i];
}
dataIndex--;
return poll;
}
template <class T>
int List<T>::size ()
{
return dataIndex+1;
}
题目4：数组中出现次数超过一半的数
题目： 一个整数数组中有一个数字出现的次数超过了数组长度的一半，请找出这个数字。如输入一个长度为9的数组{1，2，3，2，2，2，5，4，2}，由于2出现了5次，超过了数组长度的一半，因此应输出2。
解题思路
如果我们将数组排序，那么排序后位于数组中间的的数字一定是那个出现次数超过数组长度一半的数字。这个数就是统计学上的中位数。
此题关键在于快速排序算法，我们一起看看下面这张图，来理解下快排的思想。
Sorting_quicksort_anim.gif
图 4.0 快速排序过程动图，图片来源Wikipedia。
快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。
-
步骤为：
- 从数列中挑出一个元素，称为"基准"（pivot），
- 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。
测试用例
- 存在（或者不存在）次数超过数组长度一半的数。
- 特殊用例： null、空元素、 只有一个数。
编码
- Java实现
private int v4_0_solution(int[] array) {
if (array == null || array.length < 1) {
throw new IllegalArgumentException(" array is empty. ");
}
int head = 0;
int tail = array.length - 1;
// 快速排序
qSort(array, head, tail);
int middle = array.length >> 1;
int result = array[middle];
// 判断中位数是否为超过数组长度一半的数。
if (checkMoreThanHalf(array, result)) {
return result;
} else {
throw new IllegalArgumentException("not find the number.");
}
}
public void qSort(int[] arr, int head, int tail) {
// 参数合法性及结束条件
if (head >= tail || arr == null || arr.length <= 1) {
return;
}
// 取中间数为基准值
int i = head, j = tail, pivot = arr[(head + tail) / 2];
while (i <= j) {
// 处理大于等于基准数情况
while (arr[i] < pivot) {
++i;
}
while (arr[j] > pivot) {
--j;
}
// 直接互换，没有基准数归位操作
if (i < j) {
swap(arr, i, j);
++i;
--j;
} else if (i == j) {
++i;
}
}
// 递归处理基准数分隔的两个子数列。
qSort(arr, head, j);
qSort(arr, i, tail);
}
private boolean checkMoreThanHalf(int[] nums, int number) {
int times = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == number) {
times++;
}
}
return times * 2 > nums.length;
}
- C++ 实现
// 快速排序：递归方式 参考Wikipedia
void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
std::swap(arr[left], arr[right]);
}
if (arr[left] >= arr[end])
std::swap(arr[left], arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
int main()
{
//存在出现次数超过数组长度一半的数字
//int data[] = {1, 2, 3, 2, 2, 2, 5, 4, 2};
//不存在出现次数超过数组长度一半的数字
//int data[] = {4, 5, 1, 6, 2, 7, 3, 8};
// 出现次数超过数组长度一半的数字都出现在数组的前/后半部分
int data[] = {2, 2, 2, 2, 2, 1, 3, 4, 5};
//int data[] = {1, 3, 4, 5, 2, 2, 2, 2, 2};
int len = sizeof(data)/sizeof(int);
printf("length = %d \n", len);
quick_sort_recursive(data, 0, len -1);
for(int i=0;i<len;i++){
printf(" %d ", data[i]);
}
printf("\n");
int middle = len >> 1;
int result = data[middle];
if(CheckMoreThanHalf(data, len, result)){
printf("the number is %d ", result);
}else{
printf("not find the number.");
}
return 0;
}
有经验的面试官又来了，题目难度需要升下级，😶~
题目：这个题目有很多变种，其中一个引申为输入的是一个对象数组，该对象无法比较大小，只能利用equals()方法比较是否相等，此时该如何解（若要用到O(n)的辅助空间，能否避免？）。
解题思路
数组中有一个元素出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有元素出现次数的和还要多。
因此我们可以考虑在遍历数组的时候保存两个值： 一个是数组中的一个元素， 一个是次数。当我们遍历到下一个元素的时候，如果下一个元素和我们之前保存的元素相等（equals返回true），则次数加1；如果下一个元素和我们之前保存的不相等，则次数减1。如果次数为0，我们需要保存下一个元素，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的那个元素。
怎么样简单吧，还是画张图来理解一下。
数组中出现次数超过一半的数.png
图4.0 数组中出现次数超过数组长度一半的数。
注：虽然途中数组元素类型是整型，但其思想适用于任何类型。（1） 数组初始状态，times只是一个标记变量，默认为0， result为最后一次设置times=1时的那个元素，默认为NULL。（2）开始循环，i=0时，times设置为1，并将第一个元素 1 赋值给result变量。 （3）i=1时，由于此时Array[i]的值为 2 ，不等于result，所以times--，操作后times等于0，result不变。（4）i=2时，由于此时times==0，所以重新设置times=1，result= Array[2]= 3 。（5）i=3时，和（3）类似，由于此时Array[i]的为2，不等于result，所以times--，操作后times等于0，result不变还是等于3。（6）依次逻辑，一直遍历到末尾，即i=8时，逻辑同上，可以求出times=1，result=2；ok，循环结束。
到这里得出result=2，那这个2是不是我们要找的那个元素呢？ 答案是：不一定。 如果输入数组中存在次数超过超过数组长度一半的数，那result就是那个数，否则就不是。所以，我们还需要对这个数进行检查，检查过程请参看下方代码。
此思路：空间复杂度O(1),时间复杂度O(n)。
编码
- Java实现
private Object v4_1_solution(Object[] objects) {
if (objects == null || objects.length < 1) {
throw new IllegalArgumentException(" array is empty. ");
}
// 假设第一个元素就是超过长度一半的那个
Object result = objects[0];
int times = 1;
// 从第二个元素开始遍历
for (int i = 1; i < objects.length; i++) {
if (times == 0) {
// 重新设置
result = objects[i];
times = 1;
} else if (objects[i].equals(result)) {
times++;
} else {
times--;
}
}
if (checkMoreThanHalf(objects, result)) {
return result;
} else {
throw new IllegalArgumentException(" array is invalid ");
}
}
private boolean checkMoreThanHalf(Object[] objects, Object obj) {
int times = 0;
for (int i = 0; i < objects.length; i++) {
if (objects[i].equals(obj)) {
times++;
}
}
return times * 2 > objects.length;
}
// 测试类，重点在于实现了equals和hashcode方法。
private static class TestObject {
String unique;
public TestObject(String unique) {
this.unique = unique;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
TestObject that = (TestObject) o;
return unique != null ? unique.equals(that.unique) : that.unique == null;
}
@Override
public int hashCode() {
return unique != null ? unique.hashCode() : 0;
}
@Override
public String toString() {
return "TestObject{" +
"unique='" + unique + '\'' +
'}';
}
}
- C++实现
template <class T>
class Array {
private:
bool checkMoreThanHalf(T *objects,unsigned int len,T obj)
{
unsigned int times = 0;
for (int i = 0; i < len; i++) {
if (objects[i] == obj) {
times++;
}
}
return times * 2 > len;
};
public:
T v4_1_solution(T *objects,unsigned int len);
};
template <class T>
T Array<T>::v4_1_solution (T *objects,unsigned int len)
{
if (!objects || len < 1) {
throw out_of_range(" array is empty. ");
}
// 假设第一个元素就是超过长度一半的那个
T result = objects[0];
if(len == 1){
return result;
}
int times = 1;
// 从第二个元素开始遍历
for (int i = 1; i < len; i++) {
if (times == 0) {
// 重新设置
result = objects[i];
times = 1;
} else if (objects[i] == result) {
times++;
} else {
times--;
}
}
if (checkMoreThanHalf(objects,len, result)) {
return result;
} else {
throw out_of_range(" array is invalid ");
}
}
学习心得&解题套路
细心的读者可能发现了，文中解题过程大致是这样的：分析思路->测试用例->编码->调试并通过测试。你可能会问怎样才能很好的掌握算法编程呢？我的建议是：有事没事刷道题吧。勤加练习，终成大神。哈哈，请轻拍。
-
关于解题思路（详见剑指offer）
- 画图让抽象问题形象化
- 举例让抽象问题具体化
- 分解让复杂问题简单化
-
学习资源(信息大爆炸，好资源很重要)
总结
现在去大公司面试，都会有算法题，所以不是你想不想掌握它，而是公司会通过它把一部分人淘汰掉，说的可能有点吓人，但现实就是这样操作的。文中所有代码均编译运行并通过测试用例检查，由于篇幅限制，代码没有贴全，完整的可运行代码请点击链接获取： https://github.com/yangjiantao/DSAA。 由于作者水平有限，文中错误之处在所难免，敬请读者指正。
编程能力就像任何其他技能一样，也是一个可以通过刻意练习大大提高的。 --- 摘抄至LeetCode。
