如何做织梦论坛类的网站,网络运维和网站开发,外贸网站 源码,如何快速做企业网站包括商城来源#xff1a;嵌入式大杂烩数组是最基本的数据结构#xff0c;关于数组的面试题也屡见不鲜#xff0c;本文罗列了一些常见的面试题#xff0c;仅供参考。目前有以下18道题目。数组求和求数组的最大值和最小值求数组的最大值和次大值求数组中出现次数超过一半的元素求数组…来源嵌入式大杂烩数组是最基本的数据结构关于数组的面试题也屡见不鲜本文罗列了一些常见的面试题仅供参考。目前有以下18道题目。数组求和求数组的最大值和最小值求数组的最大值和次大值求数组中出现次数超过一半的元素求数组中元素的最短距离求两个有序数组的共同元素求三个数组的共同元素找出数组中唯一的重复元素找出出现奇数次的元素求数组中满足给定和的数对最大子段和最大子段积数组循环移位字符串逆序组合问题合并两个数组重排问题找出绝对值最小的元素数组求和给定一个含有n个元素的整型数组a求a中所有元素的和。可能您会觉得很简单是的的确简单但是为什么还要说呢原因有二第一这道题要求用递归法只用一行代码。第二这是我人生中第一次面试时候遇到的题意义特殊。分析简单说一下两种情况如果数组元素个数为0那么和为0。如果数组元素个数为n那么先求出前n - 1个元素之和再加上a[n - 1]即可代码// 数组求和
int sum(int*a, int n)
{return n 0 ? 0 : sum(a, n -1) a[n -1];
}求数组的最大值和最小值给定一个含有n个元素的整型数组a找出其中的最大值和最小值分析常规的做法是遍历一次分别求出最大值和最小值但我这里要说的是分治法(Divide and couquer)将数组分成左右两部分先求出左半部份的最大值和最小值再求出右半部份的最大值和最小值然后综合起来求总体的最大值及最小值。这是个递归过程对于划分后的左右两部分同样重复这个过程直到划分区间内只剩一个元素或者两个元素。代码// 求数组的最大值和最小值返回值在maxValue和minValue
void MaxandMin(int *a, int l, int r, int maxValue, int minValue)
{if(l r) // l与r之间只有一个元素{maxValue a[l] ;minValue a[l] ;return ;}if(l 1 r) // l与r之间只有两个元素{if(a[l] a[r]){maxValue a[l] ;minValue a[r] ;}else{maxValue a[r] ;minValue a[l] ;}return ;}int m (l r) / 2 ; // 求中点int lmax ; // 左半部份最大值int lmin ; // 左半部份最小值MaxandMin(a, l, m, lmax, lmin) ; // 递归计算左半部份int rmax ; // 右半部份最大值int rmin ; // 右半部份最小值MaxandMin(a, m 1, r, rmax, rmin) ; // 递归计算右半部份maxValue max(lmax, rmax) ; // 总的最大值minValue min(lmin, rmin) ; // 总的最小值
}求数组的最大值和次大值给定一个含有n个元素的整型数组求其最大值和次大值分析思想和上一题类似同样是用分治法先求出左边的最大值leftmax和次大值leftsecond再求出右边的最大值rightmax和次大值rightsecond然后合并如何合并呢分情况考虑1 如果leftmax rightmax那么可以肯定leftmax是最大值但次大值不一定是rightmax但肯定不是rightsecond只需将leftsecond与rightmax做一次比较即可。2 如果rightmax leftmax那么可以肯定rightmax是最大值但次大值不一定是leftmax但肯定不是leftsecond所以只需将leftmax与rightsecond做一次比较即可。注意这种方法无法处理最大元素有多个的情况比如3,5,7,7将返回77而不是7,5。感谢网友 从无到有靠谁人 指出。代码// 找出数组的最大值和次大值a是待查找的数组left和right是查找区间max和second存放结果
void MaxandMin(int a[], int left, int right, intmax, intsecond)
{if(left right){max a[left] ;second INT_MIN;}elseif(left 1 right){max a[left] a[right] ? a[left] : a[right] ;second a[left] a[right] ? a[left] : a[right] ;}else{int mid left (right - left) /2 ;int leftmax ;int leftsecond ;MaxandMin(a, left, mid, leftmax, leftsecond) ;int rightmax ;int rightsecond ;MaxandMin(a, mid 1, right, rightmax, rightsecond) ;if (leftmax rightmax){max leftmax ;second leftsecond rightmax ? leftsecond : rightmax ;}else{max rightmax ;second leftmax rightsecond ? rightsecond : leftmax ;}}
}求数组中出现次数超过一半的元素给定一个n个整型元素的数组a其中有一个元素出现次数超过n / 2求这个元素。据说是百度的一道题分析设置一个当前值和当前值的计数器初始化当前值为数组首元素计数器值为1然后从第二个元素开始遍历整个数组对于每个被遍历到的值a[i]1 如果a[i]currentValue则计数器值加12 如果a[i] ! currentValue 则计数器值减1如果计数器值小于0则更新当前值为a[i]并将计数器值重置为1代码// 找出数组中出现次数超过一半的元素
int Find(int* a, int n)
{int curValue a[0] ;int count 1 ;for (int i 1; i n; i){if (a[i] curValue)count ;else{count-- ;if (count 0){curValue a[i] ;count 1 ;}}}return curValue ;
}另一个方法是先对数组排序然后取中间元素即可因为如果某个元素的个数超过一半那么数组排序后该元素必定占据数组的中间位置。求数组中元素的最短距离给定一个含有n个元素的整型数组找出数组中的两个元素x和y使得abs(x - y)值最小分析先对数组排序然后遍历一次即可代码int compare(const void* a, const void* b)
{return *(int*)a - *(int*)b ;
}// 求数组中元素的最短距离
void MinimumDistance(int* a, int n)
{// Sortqsort(a, n, sizeof(int), compare) ;int i ; // Index of number 1int j ; // Index of number 2int minDistance numeric_limitsint::max() ;for (int k 0; k n - 1; k){if (a[k 1] - a[k] minDistance){minDistance a[k 1] - a[k] ;i a[k] ;j a[k 1] ;}}cout Minimum distance is: minDistance endl ;cout i i j j endl ;
}求两个有序数组的共同元素给定两个含有n个元素的有序非降序整型数组a和b求出其共同元素比如a 0, 1, 2, 3, 4b 1, 3, 5, 7, 9输出 1, 3分析充分利用数组有序的性质用两个指针i和j分别指向a和b比较a[i]和b[j]根据比较结果移动指针则有如下三种情况a[i] b[j]则i增加1继续比较a[i] b[j]则i和j皆加1继续比较a[i] b[j]则j加1继续比较重复以上过程直到i或j到达数组末尾。代码// 找出两个数组的共同元素
void FindCommon(int* a, int* b, int n)
{int i 0;int j 0 ;while (i n j n){if (a[i] b[j])i ;else if(a[i] b[j]){cout a[i] endl ;i ;j ;}else// a[i] b[j]j ;}
}这到题还有其他的解法比如对于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中元素的位置作为下一次搜索的起始点。求三个数组的共同元素给定三个含有n个元素的整型数组a,b和c求他们最小的共同元素。分析如果三个数组都有序那么可以设置三个指针指向三个数组的头部然后根据这三个指针所指的值进行比较来移动指针直道找到共同元素。代码// 三个数组的共同元素-只找最小的
void FindCommonElements(int a[], int b[], int c[], int x, int y, int z)
{for(int i 0, j 0, k 0; i x j y k z;){if(a[i] b[j]){i ;}else // a[i] b[j]{if(b[j] c[k]){j ;}else // b[j] c[k]{if(c[k] a[i]){k ;}else // c[k] a[i]{cout c[k] endl ;return ;}}}}cout Not found! endl ;
}如果三个数组都无序可以先对a, b进行排序然后对c中任意一个元素都在b和c中做二分搜索。代码// 找出三个数组的共同元素
// O(NlogN)
int UniqueCommonItem(int *a, int *b, int *c, int n)
{// sort array aqsort(a, n, sizeof(int), compare) ; // NlogN// sort array bqsort(b, n, sizeof(int), compare) ; // NlogN// for each element in array c, do a binary search in a and b// This is up to a complexity of N*2*logNfor (int i 0; i n; i){if(BinarySearch(a, n, c[i]) BinarySearch(b, n, c[i]))return c[i] ;}return - 1 ; // not found
}也可以对a进行排序然后对于b和c中任意一个元素都在a中进行二分搜索但是这样做是有问题的你看出来了么感谢网友yy_5533指正。代码// 找出三个数组唯一的共同元素
// O(NlogN)
int UniqueCommonItem1(int *a, int *b, int *c, int n)
{// sort array aqsort(a, n, sizeof(int), compare) ; // NlogN// Space for timebool *bb new bool[n] ;memset(bb, 0, n) ;bool *bc new bool[n] ;memset(bb, 0, n) ;// for each element in b, do a BS in a and mark all the common elementfor (int i 0; i n; i) // NlogN{if(BinarySearch(a, n, b[i]))bb[i] true ;}// for each element in c, do a BS only if b[i] is truefor (int i 0; i n; i) // NlogN{if(b[i] BinarySearch(a, n, c[i]))return c[i] ;}return - 1 ; // not found
}排序和二分搜索代码如下// Determine whether a contains value k
bool BinarySearch(int *a, int n, int k)
{int left 0 ;int right n - 1 ;while (left right){int mid (left right) ;if(a[mid] k)left mid 1 ;if(a[mid] k)return true ;elseright mid - 1 ;}return false ;
}// Compare function for qsort
int compare(const void* a, const void* b)
{return *(int*)a - *(int*)b ;
}小小总结一下对于在数组中进行查找的问题可以分如下两种情况处理如果给定的数组有序那么首先应该想到Binary Search所需O(logn)如果给定的数组无序那么首先应该想到对数组进行排序很多排序算法都能在O(nlogn)时间内对数组进行排序然后再使用二分搜索总的时间复杂度仍是O(nlogn)。如果能做到以上两点大多数关于数组的查找问题都能迎刃而解。找出数组中唯一的重复元素给定含有1001个元素的数组其中存放了1-1000之内的整数只有一个整数是重复的请找出这个数分析求出整个数组的和再减去1-1000的和代码略找出出现奇数次的元素给定一个含有n个元素的整型数组a其中只有一个元素出现奇数次找出这个元素。这道题实际上是一个变种原题是找出数组中唯一一个出现一次的元素下面的方法可以同时解决这两道提。所以题目就用这个广义的吧。分析因为对于任意一个数k有k ^ k 0k ^ 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 ;
}求数组中满足给定和的数对给定两个有序整型数组a和b各有n个元素求两个数组中满足给定和的数对即对a中元素i和b中元素j满足i j d(d已知)分析两个指针i和j分别指向数组的首尾然后从两端同时向中间遍历。代码// 找出满足给定和的数对
void FixedSum(int* a, int* b, int n, int d)
{for (int i 0, j n - 1; i n j 0){if (a[i] b[j] d)i ;else if (a[i] b[j] d){cout a[i] , b[j] endl ;i ;--j ;}else // a[i] b[j] d--j ;}
}最大子段和给定一个整型数组a求出最大连续子段之和如果和为负数则按0计算比如1 2 -5 6 8则输出6 8 14分析编程珠玑上的经典题目不多说了。代码// 子数组的最大和
int Sum(int* a, int n)
{int curSum 0;int maxSum 0;for (int i 0; i n; i){if (curSum a[i] 0)curSum 0;else{curSum a[i] ;maxSum max(maxSum, curSum);}}return maxSum;
}最大子段积给定一个整型数组a求出最大连续子段的乘积比如 1 2 -8 12 7则输出12 * 7 84分析与最大子段和类似注意处理负数的情况代码// 子数组的最大乘积
int MaxProduct(int *a, int n)
{int maxProduct 1; // max positive product at current positionint minProduct 1; // min negative product at current positionint r 1; // result, max multiplication totallyfor (int i 0; i n; i){if (a[i] 0){maxProduct * a[i];minProduct min(minProduct * a[i], 1);}else if (a[i] 0){maxProduct 1;minProduct 1;}else // a[i] 0{int temp maxProduct;maxProduct max(minProduct * a[i], 1);minProduct temp * a[i];}r max(r, maxProduct);}return r;
}数组循环移位将一个含有n个元素的数组向右循环移动k位要求时间复杂度是O(n)且只能使用两个额外的变量这是在微软的编程之美上看到的一道题分析比如数组 1 2 3 4循环右移1位 将变成 4 1 2 3 观察可知1 2 3 的顺序在移位前后没有改变只是和4的位置交换了一下所以等同于1 2 3 4 先划分为两部分1 2 3 | 4然后将1 2 3逆序再将4 逆序 得到 3 2 1 4最后整体逆序 得到 4 1 2 3代码// 将buffer中start和end之间的元素逆序
void Reverse( int buffer[], int start, int end )
{while ( start end ){int temp buffer[ start ] ;buffer[ start ] buffer[ end ] ;buffer[ end-- ] temp ;}
}// 将含有n个元素的数组buffer右移k位
void Shift( int buffer[], int n, int k )
{k % n ;Reverse( buffer, 0, n - k - 1) ;Reverse( buffer, n - k, n - 1 ) ;Reverse( buffer, 0, n - 1 ) ;
}稍微扩展一下,如果允许分配额外的数组,那么定义一个新的数组,然后将移位后的元素直接存入即可,也可以使用队列,将移动后得元素出对,再插入队尾即可.字符串逆序给定一个含有n个元素的字符数组a将其原地逆序。分析可能您觉得这不是关于数组的而是关于字符串的。是的。但是别忘了题目要求的是原地逆序也就是不允许额外分配空间那么参数肯定是字符数组形式因为字符串是不能被修改的这里只C/C中的字符串常量。所以和数组有关了吧只不过不是整型数组而是字符数组。用两个指针分别指向字符数组的首位交换其对应的字符然后两个指针分别向数组中央移动直到交叉。代码// 字符串逆序
void Reverse(char*a, int n)
{int left 0;int right n -1;while (left right){char temp a[left] ;a[left] a[right] ;a[right--] temp ;}
}组合问题给定一个含有n个元素的整型数组a从中任取m个元素求所有组合。比如下面的例子a 1, 2, 3, 4, 5m 3输出1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 52 3 4, 2 3 5, 2 4 5
3 4 5分析典型的排列组合问题首选回溯法为了简化问题我们将a中n个元素值分别设置为1-n代码// n选m的所有组合
int buffer[100] ;void PrintArray(int *a, int n)
{for (int i 0; i n; i)cout a[i] ;cout endl ;
}bool IsValid(int lastIndex, int value)
{for (int i 0; i lastIndex; i){if (buffer[i] value)return false;}return true;
}void Select(int t, int n, int m)
{if (t m)PrintArray(buffer, m);else{for (int i 1; i n; i){buffer[t] i;if (IsValid(t, i))Select(t 1, n, m);}}
}合并两个数组给定含有n个元素的两个有序非降序整型数组a和b。合并两个数组中的元素到整型数组c要求去除重复元素并保持c有序非降序。例子如下a 1, 2, 4, 8b 1, 3, 5, 8c 1, 2, 3, 4, 5, 8分析利用合并排序的思想两个指针i,j和k分别指向数组a和b然后比较两个指针对应元素的大小有以下三种情况a[i] b[j]则c[k] a[i]。a[i] b[j]则c[k]等于a[i]或b[j]皆可。a[i] b[j]则c[k] b[j]。重复以上过程直到i或者j到达数组末尾然后将剩下的元素直接copy到数组c中即可代码// 合并两个有序数组
void Merge(int *a, int *b, int *c, int n)
{int i 0 ;int j 0 ;int k 0 ;while (i n j n){if (a[i] b[j])// 如果a的元素小则插入a中元素到c{c[k] a[i] ;i ;}else if (a[i] b[j])// 如果a和b元素相等则插入二者皆可这里插入a{c[k] a[i] ;i ;j ;}else // a[i] b[j] // 如果b中元素小则插入b中元素到c{c[k] b[j] ;j ;}}if (i n) // 若a遍历完毕处理b中剩下的元素{for (int m j; m n; m)c[k] b[m] ;}else//j n, 若b遍历完毕处理a中剩下的元素{for (int m i; m n; m)c[k] a[m] ;}
}重排问题给定含有n个元素的整型数组a其中包括0元素和非0元素对数组进行排序要求排序后所有0元素在前所有非零元素在后且非零元素排序前后相对位置不变不能使用额外存储空间例子如下输入 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;elsereturn false;
}主函数代码。// 找出一个非递减序整数序列中绝对值最小的数
int MinimumAbsoluteValue(int* a, int n)
{// Only one number in arrayif (n 1){return a[0] ;}// All numbers in array have the same signif (SameSign(a[0], a[n -1])){return a[0] 0? a[0] : a[n -1] ;}// Binary searchint 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 -1;continue;}if (SameSign(a[l], a[m])){l m 1 ;continue;}}
}这段代码是有问题的感谢网友lingyunfish的指正你看出来了么修改后的代码如下// 找出一个非递减序整数序列中绝对值最小的数
int MinimumAbsoluteValue(int* a, int n)
{// Only one number in arrayif (n 1){return a[0] ;}// All numbers in array have the same signif (SameSign(a[0], a[n -1])){return a[0] 0? a[0] : a[n -1] ;}// Binary searchint 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;}}
}版权声明本文来源网络免费传达知识版权归原作者所有。如涉及作品版权问题请联系我进行删除。来源https://www.cnblogs.com/graphics/archive/2010/08/24/1761620.html‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧ END ‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧
