- 首页 > it技术 > >
以下是我总结的关于高频率数组系列的面试题，如有不足之处，希望大家指出
#include
#include
#include
using namespace std;
#include
#include
#include /*********************求数组中出现次数超过一半的元素*********************/
//一个数组中，一个数出现的次数超过了数组长度的一半，请找出这个数（大胃王发水贴问题）
//普通的方法是：排序（快排）一遍，中间的数字即为要找的数字，但是效率不高，在这里不做详解
//下面是时间复杂度为O（N）的算法
//思路：
//1、保存一个数和一个数出现的次数，若前一个数和后一个数若相等，次数加1，若不相等，次数减1
//2、若计算后的次数为0，则更新保存的那个数，
//3、因为要找的数字出现的次数超过了数组的一半，所以要找的数字是最后一次把次数设为1对应的数字
int Find(int array[], int size, int n)
{
int times = 1;
int ret = array[0];
for (int idx = 0;
idx <= size;
++idx)
{
if (times == 0)
{
ret = array[idx];
times = 1;
}
else if (ret == array[idx])
times++;
else
times--;
}
return ret;
}/**************************求数组中元素的最短距离******************************///给定一个含有n个元素的整型数组，找出数组中的两个元素x和y使得abs(x - y)值最小
vector FindLeastDist(vector v)
{
vectorvc;
if (v.size()==0 )
return vc;
int Curmin = abs(v[0] - v[1]);
int minimal = abs(v[0]-v[1]);
for (int i = 0;
i < v.size();
++i)
{
for (int j = i+1;
j < v.size();
++j)
{
Curmin = abs(v[i] - v[j]);
if (minimal > Curmin)
{
minimal = Curmin;
if (!vc.empty())
{
vc.pop_back();
vc.pop_back();
}
vc.push_back(v[i]);
vc.push_back(v[j]);
}
}
}
return vc;
}/************************求两个有序数组的共同元素*********************///给定两个含有n个元素的有序（非降序）整型数组a和b，求出其共同元素，比如
//arr1[] = { 0, 1, 2, 3, 4 }
//arr2[] = { 1, 3, 5, 7, 9 }
//输出 1, 3
//充分:
//利用数组有序的性质，用两个指针idx1和idx2分别指向arr1和arr2，比较arr1[idx1]和arr2[idx2]，根据比较结果移动指针，则有如下三种情况
//1. arr1[idx1] < arr2[idx2]，则idx1增加1，继续比较
//2. arr1[idx1] ==arr2[idx2]，则idx1和idx2皆加1，继续比较
//3. arr1[idx1] > arr2[idx2]，则idx2加1，继续比较
//重复以上过程直到idx1或idx2到达数组末尾。
void FindComNum(int*arr1,int size1, int*arr2,int size2)
{
if (NULL == arr1 || NULL == arr2 || size1 <1 || size2 <1)
return;
int idx1 = 0;
int idx2 = 0;
while (idx1 < size1&&idx2 < size2)
{
if (arr1[idx1] == arr2[idx2])
{
cout << arr1[idx1];
idx1++;
idx2++;
}
if (arr1[idx1] < arr2[idx2])
idx1++;
if (arr1[idx1]> arr2[idx2])
idx2++;
}
}
//这到题还有其他的解法，比如对于a中任意一个元素，在b中对其进行Binary Search，因为a中有n个元素，而在b中进行Binary Search需要logn。
//所以找出全部相同元素的时间复杂度是O(nlogn)。
//另外，上面的方法，只要b有序即可，a是否有序无所谓，因为我们只是在b中做Binary Search。如果a也有序的话，那么再用上面的方法就有点慢了，
//因为如果a中某个元素在b中的位置是k的话，那么a中下一个元素在b中的位置一定位于k的右侧，所以本次的搜索空间可以根据上次的搜索结果缩小，
//而不是仍然在整个b中搜索。也即如果a和b都有序的话，代码可以做如下修改，记录上次搜索时b中元素的位置，作为下一次搜索的起始点。/**************************求三个数组的共同元素***************************///分析:如果三个数组都有序，那么可以设置三个指针指向三个数组的头部，然后根据这三个指针所指的值进行比较来移动指针，直道找到共同元素。(方法和以上一样，这里就不写代码了)
//如果三个数组都无序，可以先对a, b进行排序，然后对c中任意一个元素都在b和c中做二分搜索。/*************************找出数组中唯一的重复元素**************************///找出出现奇数次的元素
//给定一个含有n个元素的整型数组a，其中只有一个元素出现奇数次，找出这个元素。
//这道题实际上是一个变种，原题是找出数组中唯一一个出现一次的元素，下面的方法可以同时解决这两道提。
//分析:
//因为对于任意一个数k，有k ^ k = 0，k ^ 0 = k，所以将a中所有元素进行异或，那么个数为偶数的元素异或后都变成了0，
//只留下了个数为奇数的那个元素。
int FindElementWithOddCount(int*a, int n)
{
int r = a[0];
for (int i = 1;
i < n;
++i)
{
r ^= a[i];
}return r;
}/*************************数组中值出现一次的数字**************************///题目：一个整型数组里除了两个数字之外，其它的数字都出现了两次。
//请写程序找出这两个只出现一次的数字。时间复杂度为O（n），空间复杂度为O（1）
//如：输入数组{2，4，3，6，3，2，5，5}
//输出：4，6//解题思路：
//暴力求解：排序之后，2，2，3，3，4，5，5，6，可知一个数既不和它前面的数相等，也不和它后面的数相等，
//那么这个数肯定只出现一次（不推荐）
//1、整个数组异或，得到的结果则是两个不相同的数的异或的结果(两个相同 的数都异或为0了)
//2、找出这个异或的结果的第一个1（从左向右第一个1）所在的位置，记为pos
//3、将数组中的每个元素按照pos位置是不是1分为两个子数组（逻辑分组，实际并分组）
//4、将两个子数组分别异或得到的结果即为只出现了一次的两个数size_tFindFirstBit1(int num)//找出一个数第一个bit位为1的位置
{
int pos = 0;
while (0 == (num & 1) && (pos <= sizeof(pos)* 8))
{
num >>= 1;
pos++;
}
return pos;
}//判断一个数的第n位的比特位是不是1
bool IsBit1(int num, size_t size)
{
num >>= size;
return (num & 1);
}void FindNumAppreaceOnce(int data[], int size, int num1, int num2)
{
if (NULL == data || size < 2)
return;
int ResultOR = 0;
for (int i = 0;
i < size;
i++)
{
ResultOR ^= data[i];
//0异或任意一个数，结果为任意一个数
}size_t FirstBit1Pos = FindFirstBit1(ResultOR);
//将数组按照第pos位的比特位是否为1分为两组
for (int j = 0;
j < size;
j++)
{
if (IsBit1(data[j], FirstBit1Pos))
num1 ^= data[j];
else
num2 ^= data[j];
}
cout << "出现一次的两个数:" << num1 << " " << num2 << endl;
}
void FindNumAppreaceOnce(int array[], int size)
{
int num1 = 0;
int num2 = 0;
FindNumAppreaceOnce(array, size, num1, num2);
}/***********************数字在排序数组中出现的次数**********************///数字在排序数组中出现的次数，第一想法应该是用hash方法，计算出数组中所有数据出现的次数，
//然后直接查找，时间复杂度O(n),空间复杂度O(n)。
//但是这种方法未能利用该数组是排序的特点，所以有关排序的题目，要及时联想到二分查找。
//本题就是利用的二分查找的一个变体，来求出要查找的数在数组中第一次出现和最后一次出现的位置，
//来确定数字在数组中出现的次数。
//当然在具体写程序的过程还要注意一些临界条件的判断以及特殊情况的处理（如某个数出现的位置是0
//和在数组中未找到这个数字返回为0的时候区别，我程序中用了标记来区分这两种情况）。
//二分查找时间复杂度是O(logn)，减少了时间复杂度。
//解题思路：
//用二分查找，分别找出第一个3，和最后一个3的位置，然后计算个数。int FirstKpos(int*array, int size, int start, int end, int k)
{
if (start > end)
return -1;
//没找到k返回-1
int MidIndex = (start + end) / 2;
if (array[MidIndex] == k)
{//若k前面没有k了，则k是第一次出现，返回k第一次出现的位置，
if (MidIndex == 0 || MidIndex > 0 && array[MidIndex - 1] != k)
return MidIndex;
else//k 不是第一次出现，那么就继续从k的位置前面继续找k第一次出现的位置
end = MidIndex - 1;
}
if (array[MidIndex] < k)
start = MidIndex + 1;
if (array[MidIndex]>k)
end = MidIndex - 1;
returnFirstKpos(array, size, start, end, k);
}int LastKpos(int*array, int size, int start, int end, int k)
{
if (start > end)
return -1;
//没找到k返回-1
int MidIndex = (start + end) / 2;
if (array[MidIndex] == k)
{//若k后面没有k了，则k是最后一次出现，返回k最后一次出现的位置，
if (MidIndex == size - 1 || MidIndex 1 && array[MidIndex + 1] != k)
return MidIndex;
else//k 不是最后次出现，那么就继续从k的位置后面继续找k最后次出现的位置
start = MidIndex + 1;
}
if (array[MidIndex] < k)
start = MidIndex + 1;
if (array[MidIndex]>k)
end = MidIndex - 1;
returnLastKpos(array, size, start, end, k);
}int NumbersOfK(int *array, int size, int k)
{
if (NULL == array || size < 1)
return -1;
int First = FirstKpos(array, size, 0, size - 1, k);
int Last = LastKpos(array, size, 0, size - 1, k);
if (First>-1 && Last>-1)
return Last - First + 1;
cout << "没找到" << endl;
return -1;
}/************************求数组中满足给定和的数对*************************///给定两个有序整型数组arr1和arr2，各有size个元素，求两个数组中满足给定和的数对，即对arr1中元素num1和arr2中元素num2，满足num1+num2=sum(sum已知)
//分析:
//两个指针idx1和idx2分别指向数组的首尾，然后从两端同时向中间遍历
void FixedSum(int* arr1, int* arr2, int size, int sum)
{
bool SumFlag = false;
int idx1 = 0;
int idx2 = size-1;
while (idx1=0)
{
if (arr1[idx1] + arr2[idx2] < sum)
idx1++;
if (arr1[idx1] + arr2[idx2] == sum)
{
cout << arr1[idx1] << "," << arr2[idx2] << endl;
SumFlag = true;
idx1++;
idx2--;
}
if (arr1[idx1] + arr2[idx2] >sum)
idx2--;
}
if (!SumFlag)
cout << "input sum is error" << endl;
}/*************************满足条件的和***************************/
//输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
//输出描述:
//对应每个测试案例，输出两个数，小的先输出。
vector FindNumbersWithSum(vector arr, int sum)
{
vectorvc;
if (arr.size() < 2)
return vc;
int start = 0;
int end = arr.size() - 1;
int MulCur = 0;
int MulMax = 0;
while (start != end)
{
if (arr[start] + arr[end] == sum)
{
MulCur = arr[start] * arr[end];
if (MulMax < MulCur)
{
if (vc.empty())
{
vc.push_back(arr[start]);
vc.push_back(arr[end]);
}
else
{
while (!vc.empty())
vc.pop_back();
vc.push_back(arr[start]);
vc.push_back(arr[end]);
}
}
start++;
end--;
}
else if (arr[start] + arr[end]else
end--;
}
return vc;
}/*************************把数字排序成最小的数***************************///问题描述：输入一个正整数数组，将它们连接起来排成一个数，
//输出能排出的所有数字中最小的一个。例如输入数组{32, 3 321}，
//则输出这两个能排成的最小数字321323。请给出解决问题的算法，并证明该算法。
//思路：先将整数数组转为字符串数组，然后字符串数组进行排序，最后依次输出字符串数组即可。
//这里注意的是字符串的比较函数需要重新定义，不是比较a和b，而是比较ab与 ba。如果ab < ba，则a < b；如果ab > ba，则a > b；
//如果ab = ba，则a = b。比较函数的定义是本解决方案的关键。
//这道题其实就是希望我们能找到一个排序规则，根据这个规则排出来的数组能排成一个最小的数字。int comp(const string& str1, const string &str2)
{
string s1 = str1 + str2;
string s2 = str2 + str1;
return s1//s1str1>str2---->321323，降序排列
//return s1>s2;
//s1>s2-------->str1332321,升序排列
}
void ComArrayMin(int *pArray, int num)
{
string *pStrArray = new string[num];
for (int i = 0;
i> str;
pStrArray[i] = str;
}
sort(pStrArray, pStrArray + num, comp);
//对字符串数组进行排序，默认的是升序
for (int idx = 0;
idx array2[idx2])
idx2++;
}
return count;
}
void MergeArr(int *arr1, int size1, int *arr2, int size2)
{
//求两个数组相交的元素有几个
int comm = ComNum(arr1, size1, arr2, size2);
int arrsize = size1 + size2 - comm;
int *arr = new int [arrsize];
int idx1 = 0;
int idx2 = 0;
int idx = 0;
while ((idx1if (arr1[idx1] == arr2[idx2])
{
arr[idx] = arr1[idx1];
idx1++;
idx2++;
idx++;
}
else if (arr1[idx1] < arr2[idx2])
{
arr[idx] = arr1[idx1];
idx1++;
idx++;
}
else
{
arr[idx] = arr2[idx2];
idx++;
idx2++;
}
}
while (idx1 //将数组arr1剩余的元素全部拷进arr
{
arr[idx] = arr1[idx1];
idx1++;
idx++;
}
while (idx2 //将数组arr2剩余的元素全部拷进arr
{
arr[idx] = arr2[idx2];
idx2++;
idx++;
}
int k = 0;
for (int k = 0;
k < arrsize;
k++)
{
cout << arr[k] << " ";
}
cout << endl;
delete []arr;
}/*******************合并两个数组之后仍然有序****************************///有两个排序的数组A1和A2，内存在A1的末尾有足够多的空余空间容纳A2。请实现一个函数，
//把A2中所有的数字插入到A1中，并且所有的数字是有序的
void ArrInsertSort(int arr1[], int arr2[], int leng1, int leng2)
{
if (arr1 == NULL&&arr2 == NULL)
return;
if (leng1 < leng2)//计算arr1实际元素的个数与arr1的size，如果arr1的size大于arr1的实际元素的个数加上arr2的leng2，则继续拷拷贝，否则返回
return;
int valid = leng1 - leng2 - 1;
//arr1实际元素的个数
while (valid >= 0 || leng2 >= 0)
{
if (arr1[valid]>arr2[leng2])//从arr1的后面往前插
{
arr1[leng1] = arr1[valid];
valid--;
}
else
{
arr1[leng1] = arr2[leng2];
leng2--;
}
leng1--;
//arr1的总长度--
}
}/********************二维数组中的查找**************************///题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，
//每一列都按照从上到下递增的顺序排序。完成一个函数，输入一个
//二维数组和一个整数，判断数组中是否含有该整数
bool Find(int* matrix, int ROWS, int COLS, int Num)
{
bool found = false;
if (matrix != NULL&&ROWS > 0 && COLS > 0)
{
int row = 0;
int col = COLS - 1;
while (row= 0)
{
if (matrix[row* COLS + col] == Num)
{
found = true;
break;
}
else if (matrix[row* COLS + col] < Num)
++row;
else
--col;
}
}
return found;
}/************************连续子数组的最大和**************************/
//way1 O(N^2)
bool g_invalidinput = false;
int SeqMaxSum1(int arr[], size_t size)
{//arr={1,-2,3.10,-4,7,2,-5}
if (arr == NULL&&size <= 0)
{
g_invalidinput = true;
return 0;
}
int maxsum = 0;
int sum = 0;
for (size_t i = 1;
i < size;
++i)
{
if (maxsumfor (size_t j = 0;
j < i;
++j)
{
sum += arr[j];
}
}
return maxsum;
}
//way2 O(n)
//思路：arr={1,-2,3.10,-4,7,2,-5}
//1、从第一个数开始相加，第一次求和为1，第二次求和为-1，第三次求和为2；
//但是单独一个3比前两个数字之和都大，所以第三个数字（3）求和会比从第一个数字求和
//所得结果要大。
//2、接下来从第三个位置进行求和，即3+10=13；继续求和：3+10-4=9；
//两个对比之后，保存所求的和13（可能是最大的和），保存好了继续求和：3+10-4+7=16；
//更新保存的和13为16；继续求和：3+10-4+7+2=18；更新保存的和16为18；最后一次保存的和即为
//所求的最大的和
//3、重复做1和2两个步骤即可；
//bool g_invalidinput = false;
int SeqMaxSum2(int arr[], size_t size)
{
if (arr == NULL&&size <= 0)
{
//g_invalidinput = true;
return 0;
}
int pcursum = 0;
int newsum = 0;
for (size_t idx = 0;
idx < size;
++idx)
{
pcursum += arr[idx];
if (pcursum < arr[idx])
{
pcursum = arr[idx];
}
if (newsum < pcursum)
{
newsum = pcursum;
}
}
return newsum;
}/***********************最大子段积***************************///给定一个整型数组a，求出最大连续子段的乘积，比如 1， 2， -8， 12， 7则输出12 * 7 = 84
//分析:与最大子段和类似，注意处理负数的情况//原理：先定规则在组队过程中记录下组队的最大正值和最小负值，初始都是1。遇正数最大正值继续变大，
//最小负值保持不动；遇负数把最小负值（ != 1）赋给最大正值，把最大正值乘以负值后赋值给最小负值。
//最大正值的峰值就是欲求值。
bool IsValid = true;
int MaxSubMul(int *array, int size)// int arr={1,2,-8,12,7};
2,-9,-11,-12,7};
{
if (NULL == array || size < 1)
{
IsValid = false;
return -1;
}
int maxProduct = 1;
// max positive product at current position
int minProduct = 1;
// min negative product at current position
int r = 1;
// result, max multiplication totallyfor (int i = 0;
i < size;
i++)
{
if (array[i] > 0)
{
maxProduct *= array[i];
//2
minProduct = min(minProduct * array[i], 1);
//1
}
else if (array[i] == 0)
{
maxProduct = 1;
minProduct = 1;
}
else // a[i] < 0
{
int temp = maxProduct;
//2
maxProduct = max(minProduct * array[i], 1);
minProduct = temp * array[i];
//2
}
r = max(r, maxProduct);
}
return r;
}/**************************重排问题*****************************/
//给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：
//1. 排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变
//2. 不能使用额外存储空间
//例子如下:
//输入 0, 3, 0, 2, 1, 0, 0
//输出 0, 0, 0, 0, 3, 2, 1//分析：
//此排序非传统意义上的排序，因为它要求排序前后非0元素的相对位置不变，或许叫做整理会更恰当一些。
//我们可以从后向前遍历整个数组，遇到某个位置i上的元素是非0元素时，如果a[k]为0，则将a[i]赋值给a[k]，a[k]赋值为0。
//实际上i是非0元素的下标，而k是0元素的下标
void Arrange(int* a, int n)
{
int k = n - 1;
for (int i = n - 1;
i >= 0;
--i)
{
if (a[i] != 0)
{
if (a[k] == 0)
{
a[k] = a[i];
a[i] = 0;
}
--k;
}
}
}/*******************找出绝对值最小的元素**************************///给定一个有序整数序列（非递减序），可能包含负数，找出其中绝对值最小的元素，比如给定序列 - 5, -3, -1, 2, 8 则返回1。
//由于给定序列是有序的，而这又是搜索问题，所以首先想到二分搜索法，只不过这个二分法比普通的二分法稍微麻烦点，可以分为下面几种情况
//分析：
//如果给定的序列中所有的数都是正数，那么数组的第一个元素即是结果。
//如果给定的序列中所有的数都是负数，那么数组的最后一个元素即是结果。
//如果给定的序列中既有正数又有负数，那么绝对值得最小值一定出现在正数和负数的连接处。
//为什么？因为对于负数序列来说，右侧的数字比左侧的数字绝对值小，如上面的 - 5, -3, -1,
//而对于整整数来说，左边的数字绝对值小，比如上面的2, 8，将这个思想用于二分搜索，
//可先判断中间元素和两侧元素的符号，然后根据符号决定搜索区间，逐步缩小搜索区间，直到只剩下两个元素。
bool SameSign(int a, int b)//单独设置一个函数用来判断两个整数的符号是否相同。
{
if (a * b > 0)
return true;
else
return false;
}
// 找出一个非递减序整数序列中绝对值最小的数
int MinimumAbsoluteValue(int* a, int n)
{
// Only one number in array
if (n == 1)
{
return a[0];
}
// All numbers in array have the same sign
if (SameSign(a[0], a[n - 1]))
{
return a[0] >= 0 ? a[0] : a[n - 1];
}
// Binary search
int l = 0;
int r = n - 1;
while (l < r)
{
if (l + 1 == r)
{
return abs(a[l]) < abs(a[r]) ? a[l] : a[r];
}int m = (l + r) / 2;
if (SameSign(a[m], a[r]))
{
r = m;
continue;
}
else
{
l = m;
continue;
}
}
}
推荐阅读
