转载声明：文章链接：https://blog.csdn.net/qq_45034708/article/details/115447938
数组中重复的数字
题目：在一个长度为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的数字比较，如果相同就找到了一个重复的数字，否则交换这两个数字。
#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二维数组中的查找
题目：在一个二维数组中，每一行都是按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样一个二维数组和一个整数，判断数组中是否含有该整数
对于排序数组中的查找，我们第一反应是用二分查找，但是在这个二维数组中，二分会存在两个区域（蓝、黄），而且两个区域间还会重叠（绿），处理起来较复杂。
我们考虑选取右上角（15）作为起点，设查找的数字是10，首先15大于10，那15这一列后面的数是比15还大的，所以15这一列排除；然后分析剩下的列，仍取右上角（9），9小于10，那9这一行前面的数也是比9小的，排除9这一行；然后分析11，11大于10同样排除这一列，接下来的右上角就是我们需要找的数10，退出循环。
#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)
但这样还存在一个BUG，就是判断中间指针既大于等于第一个指针，又小于等于第二个指针的情况，此时就无法判断属于哪一个子数组，移动哪一个指针，这种情况下只能采用顺序查找暴力的方法了。
#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)
#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)
#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最小的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 ii个数字结尾的子数组的最大和，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的过程：
#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
帖子还没人回复快来抢沙发