文章目錄

陣列中重復的數字
二維陣列中的查找
旋轉陣列的最小數字
調整數字順序使奇數位于偶數前面
陣列中出現次數超過一半的數字
最小的k個數
連續子陣列的最大和
數字序列中某一位的數字
把陣列排成最小的數
和為s的數字
陣列中數字出現的次數

在這里插入圖片描述

陣列中重復的數字

題目：在一個長度為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 ) O(n) 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

（~~插播反爬資訊~~ ）博主CSDN地址：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*10^n-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

原創不易，請勿轉載（~~本不富裕的訪問量雪上加霜~~ ）
博主首頁：https://wzlodq.blog.csdn.net/
微信公眾號：唔仄lo咚鏘
如果文章對你有幫助，記得一鍵三連?

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/273273.html

標籤：其他

上一篇：SNMP實作交換機的資訊采集——MIB

下一篇：[譯] APT分析報告：08.漏洞利用圖譜–通過查找作者的指紋來尋找漏洞

陣列面試題-大力出奇跡？