数组面试题-大力出奇迹？

喜欢ヅ旅行 2022-10-22 07:58 156阅读 0赞

### 文章目录 ###

*  数组中重复的数字
 *  二维数组中的查找
 *  旋转数组的最小数字
 *  调整数字顺序使奇数位于偶数前面
 *  数组中出现次数超过一半的数字
 *  最小的k个数
 *  连续子数组的最大和
 *  数字序列中某一位的数字
 *  把数组排成最小的数
 *  和为s的数字
 *  数组中数字出现的次数

相关推荐（[面试][Link 1]专栏查看更多）

*  [链表面试题(动图详解)-明明做出来了却为什么没有Offer?][-_Offer]
 *  [二叉树面试题-你已经是棵成熟的二叉树了，要学会自己解题][-]
 *  [数组面试题-大力出奇迹？][- 1]

![在这里插入图片描述][20210406212100643.jpg_pic_center]

# 数组中重复的数字 #

--------------------

> 题目：在一个长度为n的数组里的所有数字都在0~n-1的范围内。数组中某些数字时重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

一般做法可能是吧数组排序，然后只需从头到尾扫描排序后的数组就可以了，复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)。还可以借助哈希表，判断是否存在重复数字，时间复杂度是 O ( n ) O(n) O(n)但是也需要 O ( n ) O(n) O(n)大小的空间。

我们来看一种时间复杂度是 O ( n ) O(n) O(n)且空间复杂度是 O ( 1 ) O(1) O(1)的做法。因为数字范围是0~n-1，当没有重复数字时，数字i将出现在下标为i的位置，当有重复数字时有些位置就可能存在多个数字。从头到尾扫描这个数字中的每个数字，当扫描到下标为i的数字是，比较这个数字（设为m）是否和i相同，若相同则继续扫描下一个数字；否则拿它和下标为m的数字比较，如果相同就找到了一个重复的数字，否则交换这两个数字。  
![在这里插入图片描述][20210405235613752.gif_pic_center]

#include<bits/stdc++.h>
    using namespace std;
    bool duplicate(int numbers[], int length, int* dulication) { 
    	if (numbers == nullptr || length <= 0) //空
    		return false;
    	for (int i = 0; i < length; i++)
    		if (numbers[i] < 0 || numbers[i] >= length)//非0~n-1
    			return false;
    	for (int i = 0; i < length; i++) { 
    		while (numbers[i] != i) { 
    			if (numbers[i] == numbers[numbers[i]]) { 
    				*dulication = numbers[i];
    				return true;
    			}
    			swap(numbers[i], numbers[numbers[i]]);
    		}
    	}
    	return false;
    }
    int main() { 
    	int a[7] = {  3,0,2,1,2,4,0 };
    	int ans = -1;
    	if (duplicate(a, 7, &ans))
    		printf("重复数为%d", ans);
    	else printf("无重复数");
    	return 0;
    }
    //运行结果：重复数为2

# 二维数组中的查找 #

--------------------

> 题目：在一个二维数组中，每一行都是按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否含有该整数

对于排序数组中的查找，我们第一反应是用二分查找，但是在这个二维数组中，二分会存在两个区域（蓝、黄），而且两个区域间还会重叠（绿），处理起来较复杂。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center]  
我们考虑选取右上角（15）作为起点，设查找的数字是10，首先15大于10，那15这一列后面的数是比15还大的，所以15这一列排除；然后分析剩下的列，仍取右上角（9），9小于10，那9这一行前面的数也是比9小的，排除9这一行；然后分析11，11大于10同样排除这一列，接下来的右上角就是我们需要找的数10，退出循环。  
![在这里插入图片描述][20210406131915901.gif_pic_center]

#include<bits/stdc++.h>
    using namespace std;
    bool find(int *a, int n, int m, int num) { 
    	bool found = false;
    	int i = 0, j = m - 1;
    	while (i < n && j >= 0) { 
    		if (*(a+i*n+j) > num)
    			j--;
    		else if (*(a + i * n + j) < num)
    			i++;
    		else { 
    			found = true;
    			printf("%d %d\n", i, j);
    			break;
    		}
    	}
    	return found;
    }
    int main() { 
    	int a[5][4] = {  1,3,8,9,15,2,4,10,11,16,4,6,11,12,17,6,11,12,15,21 };
    	if (find((int*)a, 5, 4, 10))
    		printf("找到了");
    	else printf("找不到");
    	return 0;
    }
    /*运行结果 1 2 找到了 */

# 旋转数组的最小数字 #

--------------------

> 题目：把一个数组最开始的若干元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。

直观做法可能就是遍历数组找到最小数字即可，复杂度是 O ( n ) O(n) O(n)，但就完全没用到给定条件，事情不会这么简单。

其实旋转数组可以看成由两个有序子数组组成的，最小元素刚好就是这两个子数组的分界线，而对于有序来说，可以尝试二分。分别用两个指针指向第一个元素和最后一个元素，然后求出中间元素，若中间元素位于前面子数组（大于等于第一个指针的值），说明最小元素应位于中间元素后面，把第一个指针移到中间；否则位于后面子数组（小于等于第二个指针）则移动第二个指针，当两个指针相邻时，第二个指针值就是答案。复杂度是 O ( l o g n ) O(logn) O(logn)  
![在这里插入图片描述][20210406153259837.gif_pic_center]  
但这样还存在一个BUG，就是判断中间指针既大于等于第一个指针，又小于等于第二个指针的情况，此时就无法判断属于哪一个子数组，移动哪一个指针，这种情况下只能采用顺序查找暴力的方法了。  
![在这里插入图片描述][20210406153858737.png_pic_center]

#include<bits/stdc++.h>
    using namespace std;
    int Min(int* a, int len) { 
    	if (a == nullptr || len <= 0)
    		throw new exception();
    	int l = 0, r = len - 1;
    	int mid = 0;//注意旋转0个元素时，答案是第0个元素
    	while (a[l] >= a[r]) { 
    		if (r - l == 1) { 
    			mid = r;
    			break;
    		}
    		mid = (l + r) >> 1;
    		if (a[l] == a[mid] && a[mid] == a[r]) { 
    			int rtn = a[0]; //三指针相等则暴力
    			for (int k = 1; k < len; k++)
    				rtn = min(rtn, a[k]);
    			mid = rtn;
    			break;
    		}
    		if (a[l] <= a[mid])
    			l = mid;
    		else if (a[r] >= a[mid])
    			r = mid;
    	}
    	return a[mid];
    }
    int main() { 
    	int a[6] = { 4,5,6,1,2,3 };
    	printf("%d", Min(a, 6));
    	return 0;
    }
    //运行结果：1

# 调整数字顺序使奇数位于偶数前面 #

--------------------

> 题目：输入一个整数数组，实现一个函数来调整该数组中数组的顺序，使得所有奇数位于数组前半部分，所有偶数位于数组后半部分

最笨的方法无非就是遍历数组，每当遇到一个偶数，就把他后面的数往前挪，时间复杂度时 O ( n 2 ) O(n^2) O(n2)。

我们可以定义维护指针，一个从前向后维护奇数，一个从后向前维护偶数，当第一个指针遇到偶数时，就移动第二个指针寻找一个奇数，然后交换这两个数字，当两指针相遇则退出。复杂度是 O ( n ) O(n) O(n)  
![在这里插入图片描述][20210406162610653.gif_pic_center]

#include<bits/stdc++.h>
    using namespace std;
    void Reorder(int* a, int len) { 
    	if (a == nullptr || len <= 0)
    		return;
    	int l = 0, r = len - 1;
    	while (l < r) { 
    		while (l < r && a[l] % 2 == 1)//移动第一个指针直到偶数
    			l++;
    		while (l < r && a[r] % 2 == 0)//移动第一个指针直到奇数
    			r--;
    		swap(a[l], a[r]);
    	}
    }
    int main() { 
    	int a[6] = {  1,2,3,4,5,6 };
    	Reorder(a, 6);
    	for (int i = 0; i < 6; i++)
    		printf("%d ", a[i]);
    	return 0;
    }
    //运行结果：1 5 3 4 2 6

# 数组中出现次数超过一半的数字 #

--------------------

> 题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

一般做法是把数组排序，然后中位数就是答案，时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)。

**解法二：**  
分析发现，数组中一个数字出现次数超过数组一半，也就是说其他所有数字出现次数加起来也没有它多。因此当我们遍历下一个数字的时候，若和上一个数字相同则次数加一；若不同则次数减一，当次数为0的时候，需要更新保存的数字并设次数为1。复杂度是 O ( n ) O(n) O(n)  
![在这里插入图片描述][2021040617184632.gif_pic_center]

#include<bits/stdc++.h>
    using namespace std;
    int moreThanHalf(int* a, int len) { 
    	if (a == nullptr || len <= 0)
    		throw new exception();
    	int num = a[0];
    	int cnt = 1;
    	for (int i = 1; i < len; i++) { 
    		if (cnt == 0) { 
    			num = a[i];
    			cnt = 1;
    		}
    		else if (a[i] == num)
    			cnt++;
    		else cnt--;
    	}
    	return num;
    }
    int main() { 
    	int a[6] = {  1,2,2,2,3 };
    	printf("%d", moreThanHalf(a, 5));
    	return 0;
    }
    //运行结果：2

> （插播反爬信息 ）博主CSDN地址：[https://wzlodq.blog.csdn.net/][https_wzlodq.blog.csdn.net]

# 最小的k个数 #

--------------------

> 题目：输入n个整数，找出其中最小的k个数。

一般做法还是排序，然后输出前k的数即可，复杂度是 O ( n l o g n ) O(nlogn) O(nlogn)。

我们可以创建一个大小为k的数据容器来存储最小的k个数字，每次读入一个数的时候，判断容器中是否已有k个数据，没有的话则放入，有的话则比较容器中的最大值，若大于当前数则替换之，保持容器中是目前最小的k个数，复杂度是 O ( n l o g k ) O(nlogk) O(nlogk)，适合海量数据。

#include<bits/stdc++.h>
    using namespace std;
    void getLeastK(int* a,int len, int k) { 
    	if (a == nullptr || k <= 0 || k > len)
    		return;
    	multiset<int,greater<int>>s;//可重复大根堆
    	multiset<int, greater<int>>::iterator it;
    	for (int i = 0; i < len; i++) { 
    		if (s.size() < k)
    			s.insert(a[i]);
    		else { 
    			it = s.begin();
    			if (*it > a[i]) { 
    				s.erase(it);
    				s.insert(a[i]);
    			}
    		}
    	}
    	for (it = s.begin(); it != s.end(); it++)
    		printf("%d ", *it);
    }
    int main() { 
    	int a[6] = {  1,4,5,2,2 };
    	getLeastK(a, 5, 3);
    	return 0;
    }
    //运行结果：2 2 1

# 连续子数组的最大和 #

--------------------

> 题目：输入一个整型数组，数组里有正数也有负数。数组中一个或连续多个整数组成一个子数组。求所有数组的和的最大值，要求时间复杂度是 O ( n ) O(n) O(n)。

当前面累加的和小于0时，则抛弃前面的，从当前数开始累加，否则加上前面的累加和，动态的维护一个最大值。此外也可以用动态规划求解，设 d p \[ i \] dp\[i\] dp\[i\]表示第 i i i个数字结尾的子数组的最大和， d p \[ i \] = m a x ( a \[ i \] , d p \[ i − 1 \] + a \[ i \] ) dp\[i\]=max(a\[i\],dp\[i-1\]+a\[i\]) dp\[i\]=max(a\[i\],dp\[i−1\]\+a\[i\])。

#include<bits/stdc++.h>
    using namespace std;
    int getMaxSub(int* a,int len) { 
    	int* dp = new int[len];
    	dp[0] = a[0];
    	for (int i = 1; i < len; i++) { 
    		dp[i] = max(a[i], dp[i - 1] + a[i]);
    	}
    	int mx = dp[0];
    	for (int i = 1; i < len; i++)
    		mx = max(mx, dp[i]);
    	return mx;
    }
    int main() { 
    	int a[7] = {  1,4,-5,2,2 ,-1,3 };
    	printf("%d", getMaxSub(a, 7));
    	return 0;
    }
    //运行结果：6

# 数字序列中某一位的数字 #

--------------------

> 题目：数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中第5位（从0开始计数）是5，第13位是1，第19位是4等等。请写一个函数，求任意第n位对应的数字。

笨方法就是直接构造序列，然后求出第n位。但是我们有更快的方法，找出某些规律从而跳过若干数字。

首先只有0-9这10个一位数，然后是10-99这90个两位数，然后是100-999这900个三位数，以此类推，不难发现，n≠1时，共有9\*10n-1个n位数，这样我们就能跳过若干位，直接到第n位所对应的数字，然后再去确定是这个数字的第几位。

#include<bits/stdc++.h>
    using namespace std;
    int digitAtIndex(int index) { 
    	if (index < 0)
    		return -1;
    	int n = 1;//n位数
    	while (1) { //找到位于几位数之间
    		int cnt = n == 1 ? 10 : 9 * pow(10, n - 1);//n位数个数
    		if (index < cnt * n)
    			break;
    		index -= n * cnt;
    		n++;
    	}
    	int num = n == 1 ? 0 : pow(10, n - 1);//n位数的第一个数
    	num += index / n;//index位于第几个数
    	int r = n - index % n;//这个数的第几位
    	for (int i = 1; i < r; i++)
    		num /= 10;
    	return num % 10;
    }
    int main() { 
    	printf("第1位：%d\n", digitAtIndex(1));
    	printf("第5位：%d\n", digitAtIndex(5));
    	printf("第13位：%d\n", digitAtIndex(13));
    	printf("第19位：%d\n", digitAtIndex(19));
    	return 0;
    }
    /*运行结果 第1位：1 第5位：5 第13位：1 第19位：4 */

# 把数组排成最小的数 #

--------------------

> 题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接处的所有数字中最小的一个。例如，输入数组\{3,32,321\}，则能排成最小数字是321323。

直接用全排列的话，肯定超时，而且还是一个隐形的大数问题。一个直观的解决方法就是先把数字转成成字符串，把数字n和m拼接起来的到nm和mn，它们的位数是相同的，因此比较他们的大小只需要按照字符串大小的比较规则就可以了，排序之后的顺序组成的数字就是最小的数，证明略。

#include<bits/stdc++.h>
    using namespace std;
    bool cmp(string a,string b){ 
    	string c=a+b;
    	string d=b+a;
    	return c<d;
    }
    void printMin(int* a, int len) { 
    	if (a == nullptr || len <= 0)
    		return;
    	string* s = new string[len];
    	char* c = new char[len];
    	for (int i = 0; i < len; i++) { 
    		sprintf(c, "%d", a[i]);
    		s[i] = c;
    	}
    	sort(s, s + len,cmp);
    	for (int i = 0; i < len; i++)
    		cout << s[i];
    }
    int main() { 
    	int a[3] = {  3,32,321 };
    	printMin(a, 3);
    	return 0;
    }
    //运行结果：321323

# 和为s的数字 #

--------------------

> 题目：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

由于数组是递增的（也可以自己排序下），那我们可以用双指针类似尺取法的思路来求解。定义两个指针，指向第一个和最后一个元素，当这两个元素的和大于s时，则把第二个指针向前移动，否则向后移动第二个指针即可。

比如数组\{2,4,5,7,11,15\}求和为16的过程：  
![在这里插入图片描述][20210406204709673.gif_pic_center]

#include<bits/stdc++.h>
    using namespace std;
    void findSum(int* a, int len,int s) { 
    	if (a == nullptr || len <= 0)
    		return;
    	int l = 0, r = len - 1;
    	while (l < r) { 
    		int cur = a[l] + a[r];
    		if (cur == s) { 
    			printf("%d %d", a[l], a[r]);
    			return;
    		}
    		if (cur > s)
    			r--;
    		else l++;
    	}
    	printf("找不到");
    }
    int main() { 
    	int a[6] = {  2,4,5,7,11,15 };
    	findSum(a, 6, 16);
    	return 0;
    }
    //运行结果：5 11

# 数组中数字出现的次数 #

--------------------

> 题目：求数组中只出现一次的两个数字。  
> 一个整型数组里除了两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求是否复杂度时 O ( n ) O(n) O(n)，空间复杂度是 O ( 1 ) O(1) O(1)。

我们想到异或运算的一个性质：任何一个数字异或他自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每个数字，那么最终结果刚好是那个只出现一次的数字，那些出现两次以上的数字全部在异或中抵消了。

可这道题目是有两个只出现一次的数字。怎么拆成两个子数组呢？我们先遍历数组全部异或一遍，得到的结果就是那两个数字的异或结果，由于这两个数字不同，所以异或结果不为0，在二进制中至少有一位为1，那么我们就可以根据这一位是不是为1，把数字划分成两个子数组，然后就能求解了。而且相同的数不可能分别分配到两个子数组中，因为它们的二进制也是相同的。

#include<bits/stdc++.h>
    using namespace std;
    void findOnce(int* a, int len) { 
    	if (a == nullptr || len <= 0)
    		return;
    	int XOR = 0;
    	for (int i = 0; i < len; i++) //求异或值
    		XOR ^= a[i];
    	int idx = 0;
    	while ((XOR & 1) == 0) { //求最右的1
    		XOR >>= 1;
    		idx++;
    	}
    	int n=0, m=0;//两个子数组分别异或
    	for (int i = 0; i < len; i++) { 
    		if (((a[i] >> idx) & 1) == 0)
    			n ^= a[i];
    		else m ^= a[i];
    	}
    	printf("%d %d", n, m);
    }
    int main() { 
    	int a[8] = {  2,4,3,4,6,3,5,2 };
    	findOnce(a, 8);
    	return 0;
    }
    //运行结果：6 5

> **原创不易，请勿转载**（本不富裕的访问量雪上加霜 ）  
> 博主首页：[https://wzlodq.blog.csdn.net/][https_wzlodq.blog.csdn.net]  
> 微信公众号：[`吾仄lo咚锵`][lo]  
> *如果文章对你有帮助，记得一键三连❤*

[Link 1]: https://blog.csdn.net/qq_45034708/category_10920342.html
[-_Offer]: https://wzlodq.blog.csdn.net/article/details/115213208
[-]: https://wzlodq.blog.csdn.net/article/details/115256537
[- 1]: https://wzlodq.blog.csdn.net/article/details/115447938
[20210406212100643.jpg_pic_center]: /images/20221022/5eecb0b41bc74c2cb9168474b760582c.png
[20210405235613752.gif_pic_center]: /images/20221022/89ae0508218f46959476b0cd72b38b9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1MDM0NzA4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/f3e8db9a53bc4bd7a7db6a2e19b7bb2d.png
[20210406131915901.gif_pic_center]: /images/20221022/ebf34c2a985147b6941ff3f9a34bc11e.png
[20210406153259837.gif_pic_center]: /images/20221022/bfae3147fecf413f8af98f0a8528801d.png
[20210406153858737.png_pic_center]: /images/20221022/a20c79392bdc4919b9de007e0bf788f3.png
[20210406162610653.gif_pic_center]: /images/20221022/e00be196dfd24022bddb8db63ed62a4e.png
[2021040617184632.gif_pic_center]: /images/20221022/a0ca9974982c49fcb962c782515a1e4e.png
[https_wzlodq.blog.csdn.net]: https://wzlodq.blog.csdn.net/
[20210406204709673.gif_pic_center]: /images/20221022/0eaeca4c7071405baf2499437b8a9b4a.png
[lo]: https://mp.weixin.qq.com/mp/profile_ext?action=home&__biz=MzkwMzE2Nzg4MQ==#wechat_redirect