[几道面试题]供大家思考着玩
老实说，我觉得要有代码出现，思路固然非常重要，但是能快速写出正确的代码也很重要。
因为我面试的时候，就有这些要求。
1）一个数组，长度为N，为循环有序的。找出其中的最小值
所谓循环有序就是 [ 4 5 6 1 2 3] 这种，1是我们要找的。
时间复杂度你们肯定比我清楚。写出代码
2）两个数组，长度分别为N，都有序，找到两个数组中，第N小的数字。
例如[1 2 3 4 6] [5 7 8 9 10],那么5是正确的答案。写出代码
3）一个数组长度为N，找出其中K个最大的数字。写出代码。
我不是来求代码的，我是来放分的。
[解决办法]
第一个简单，stl里min/max是现成的，boost里甚至提供了min_max
第三个简单，n_th在stl里也是现成的
第二个，貌似没有现成的，用stl的set_union吧。
[解决办法]
第三题我只列出最大的数字，无排序，因为题目无此要求
inline单纯是不想把.hpp和.cpp分开写，正式的程序不会用
#ifndef INTERVIEW_02_HPP#define INTERVIEW_02_HPP#include <algorithm>#include <functional>#include <iterator>#include <iostream>inline void sort_one(){ size_t array_1[] = {4 ,5 ,6 ,1 ,2 ,3}; std::nth_element(std::begin(array_1), std::begin(array_1) + 1, std::end(array_1) ); std::cout<<array_1[0]<<std::endl;}inline void sort_two(){ size_t array_1[] = {1, 2, 3, 4, 6}; size_t array_2[] = {5, 7, 8, 9, 10}; size_t const size_1 = sizeof(array_1) / sizeof(size_t); size_t const size_2 = sizeof(array_2) / sizeof(size_t); size_t result[size_1 + size_2]; std::copy(std::begin(array_1), std::end(array_1), std::begin(result)); std::copy(std::begin(array_2), std::end(array_2), std::begin(result) + size_1); std::inplace_merge(std::begin(result), std::begin(result) + size_1, std::end(result) ); std::copy(std::begin(result), std::end(result), std::ostream_iterator<size_t>(std::cout, ", ")); size_t number = 0; std::cout << std::endl << "input number : "; std::cin>>number; if(number < sizeof(result) ) std::cout<<result[number];}inline void sort_three(){ size_t array_1[] = {4 ,5 ,6 ,1 ,2 ,3}; std::cout<<"input the numbers you want to get" << std::endl; size_t number = 0; std::cin>>number; size_t const size = sizeof(array_1) / sizeof(size_t); if(number < sizeof(size)) { std::nth_element(std::begin(array_1), std::begin(array_1) + size, std::end(array_1), std::greater<size_t>() ); std::copy(std::begin(array_1), std::begin(array_1) + number, std::ostream_iterator<size_t>(std::cout, ", ")); }}#endif // INTERVIEW_02_HPP
[解决办法]
第二题有错
if(number < sizeof(result) )
[解决办法]
1. 5分钟。有a[i]==a[i+1]的情况undefined behavior
int min(const vector<int>& vec){ if(vec.size() == 0) return 0; if(vec.size() == 1) return vec[0]; int l = 0, r = vec.size() - 1; if(vec[0] < vec[r]) return vec[0]; while(l+1 < r) { int mid = (l+r)/2; if(vec[mid] > vec[l]) l = mid; else r = mid; } return vec[r];}
[解决办法]
}
int Min2( int a[], int b[], int n )
{
int i = 0, j = 0, k;
for( k = 1; k < n; k++ )
{
if( a[i] < a[j] )
{
j++;
}
else
{
i++;
}
}
if( a[i] < a[j] )
{
return a[i];
}
else
{
return b[i];
}
}
void Max( int a[], int n, int k )
{
int i, j, max, t;
for( i = 1; i <= k; i++ )
{
max = i-1;
for( j = i; j <n; k++ )
{
if( a[max] < a[j] )
{
max = j;
}
}
if( max != i-1 )
{
t = a[max];
a[max] = a[i-1];
a[i-1] = t;
}
}
}
[解决办法]
第一题，第三题用STL解复杂度应该是线性时间（平均）
如果楼主不接受STL，那我只好重造一次轮子了，稍待
int search(int array[], int start, int end){ if(start > end){ return -1; } int mid = start + (end - start) / 2; int start_value = array[start]; int middle_value = array[mid]; int end_value = array[end]; if(start_value <= middle_value) { if(start_value <= end_value) return start_value; else return search(array, mid + 1, end); } else return search(array, start, mid);}
[解决办法]
第一题 ：
#include "iostream"using namespace std;int FindMinValue(const int* iSrc, const int len){ if(abs(*(iSrc+0) - *(iSrc+len-1)) == len-1) {//首尾相减等于数组长度：正好是最大值和最小值，直接返回 return *(iSrc+0) < *(iSrc+len-1) ? *(iSrc+0) : *(iSrc+len-1); } int tmpVal = (*iSrc > *(iSrc+len-1) ? 0 : len-1); int endFlg = tmpVal - 1; while(tmpVal != endFlg) { if(tmpVal + 1 == len) { tmpVal = 0; } if(*(iSrc+tmpVal) < *(iSrc+tmpVal+1)) {//直到找到转折点 例如本例的 6 到 1 ++ tmpVal; continue; } break; } return iSrc[tmpVal+1];}int main(){ const int LEN = 6; const int iArray[LEN] = {4,5,6,1,2,3}; int result = FindMinValue(iArray, LEN); cout << "The minimem is : " << result << endl; system("pause"); return 0;}
[解决办法]
#include "iostream"using namespace std;int FindMinValue(const int* iSrc, const int len){ if(abs(*(iSrc+0) - *(iSrc+len-1)) == len-1) {//首尾相减等于数组长度：正好是最大值和最小值，直接返回 return *(iSrc+0) < *(iSrc+len-1) ? *(iSrc+0) : *(iSrc+len-1); } int tmpVal = (*iSrc > *(iSrc+len-1) ? 0 : len-1); int endFlg = tmpVal - 1; while(tmpVal != endFlg) { if(tmpVal + 1 == len) { tmpVal = 0; } if(*(iSrc+tmpVal) < *(iSrc+tmpVal+1)) {//直到找到转折点 例如本例的 6 到 1 ++ tmpVal; continue; } break; } return iSrc[tmpVal+1];}int main(){ const int LEN = 6; const int iArray[LEN] = {4,5,6,1,2,3}; int result = FindMinValue(iArray, LEN); cout << "The minimem is : " << result << endl; system("pause"); return 0;}
[解决办法]
1）一个数组，长度为N，为循环有序的。找出其中的最小值
所谓循环有序就是 [ 4 5 6 1 2 3] 这种，1是我们要找的。
时间复杂度你们肯定比我清楚。写出代码
//2分查找O(log n)f(arr){ if(size(arr)==1) if(end(arr)==end(g_arr)) return begin(g_arr) return end(arr) l,r= 2分arr; x; if( begin(l)> end(l) ) x= l; if( begin(r)> end(r) ) x= r; return f(x);}
[解决办法]
我来YY下思路。。
第一题 lgn 二分 假设有序为递增- -||
数组元素为a[1]...a[n]
if a[n]>=a[1],那么最小元素即为a[1] 如果为单调递增
else 二分搜索最小元素 search(l,r) -》search(1,n-1) 从1..n-1这些位置找出比a[n]小的最小的元素
if(l==r) return a[l]; 如果只剩下一个元素。。就他了
m=(l+r)>>1;
if(a[m]>a[n]) search(m+1,r); 如果中间元素比a[n]大。那么最小元素肯定在后面
else search(l,m); 否则就在左面
第二题 lgn 二分递归 假设有序为递增
数组元素为a[1]...a[n], b[1]...b[n]
求解search(al,ar,bl,br,s)->search(1,n,1,n,n) 在a数组al->ar,b数组bl->br找出第s小的元素
如果s为奇数 am = (al+ar)>>1, bm = (bl+br)>>1
if(s==1) return a[al]<b[bl]?a[al]:b[bl];
if(a[am]>b[bm]) return min(b[bm],search(al,am-1,bm+1,br,s/2)); bl->bm是肯定在s小范围
else return min(a[am],search(am+1,ar,bl,bm-1,s/2)); al->am肯定在s小范围内
如果s为偶数 am = (al+ar+1)>>1, bm = (bl+br+1)>>1
if(a[am]>b[bm]) return min(b[bm-1],search(al,am-1,bm,br,s/2)); bl->bm-1肯定在s小范围
else return min(a[am-1],search(am,ar,bl,bm-1,s/2)); al->am-1肯定在s小范围内
第三题 我只知道nlogk
建立大小为k的最小堆。。。
如果堆元素<k，那么直接添加到堆
否则如果堆顶元素比当前元素大。。则下一个元素
否则堆顶元素去掉，将当前元素添加到堆
[解决办法]
template<typename ForwardItr>inline std::vector<typename std::iterator_traits<ForwardItr>::value_type> constmax_2(ForwardItr first, ForwardItr last, size_t number){ if(first == last) return std::vector<int>(); if(static_cast<size_t>(std::distance(first, last)) < number ) return std::vector<int>(); typedef typename std::iterator_traits<ForwardItr>::value_type value_type; std::vector<value_type> heap(first, first + number); std::make_heap(std::begin(heap), std::end(heap), std::greater<value_type>() ); std::advance(first, number); while(first != last) { if(heap[0] < *first) { std::pop_heap (std::begin(heap), std::end(heap)); heap.pop_back(); heap.push_back(*first); std::push_heap(std::begin(heap), std::end(heap) ); } ++first; } return heap;}inline void sort_three_01(){ int array_1[] = {77, 88, 0, 4, 4 ,5 ,6 ,1 ,2 ,3, 9, 10, 20}; std::vector<int> result = max_2(std::begin(array_1), std::end(array_1), 2); for(int const data : result) std::cout << data << std::endl;}
[解决办法]
写了第一题的
int Min(int a[], int n){ int left = 0; int right = n-1; int mid = 0; int min = a[n-1]; while(left <= right) { if(left == right) return min; mid = (left + right) >> 1; if(a[mid] > min) { left = mid + 1; } else { min = a[mid]; right = mid; } }}
[解决办法]
第一问看起来容易 只要二分 但是要过掉 {2, 2, 1, 1, 2, 2} 这样的数据还要比较细心才行
第二问也还是 divide and conquer
第三问就是模范quick sort了
下面是代码 不过很tricky的数据没有试过
#include <stdio.h>// 1）一个数组，长度为N，为循环有序的。找出其中的最小值// 所谓循环有序就是 [ 4 5 6 1 2 3] 这种，1是我们要找的。// 时间复杂度你们肯定比我清楚。写出代码int bisecmin(int list[], int n) { int lower = 0, upper = n - 1, mid; if (list[upper] > list[lower]) return list[lower]; do { mid = lower + (upper - lower) / 2; if (list[lower] <= list[mid]) lower = mid + 1; else upper = mid; } while (list[lower] > list[upper]); return list[lower];}void test_bisecmin() { int i, min; int list[][6] = { {1, 2, 3, 4, 5, 6}, {2, 3, 4, 5, 6, 1}, {3, 4, 5, 6, 1, 2}, {4, 5, 6, 1, 2, 3}, {5, 6, 1, 2, 3, 4}, {6, 1, 2, 3, 4, 5}, {1, 1, 1, 1, 1, 1}, {2, 2, 1, 1, 2, 2} }; int list0[] = {1}; printf("test_bisecmin\n"); for (i = 0; i < 8; i++) { min = bisecmin(list[i], 6); printf("%d\n", min); } min = bisecmin(list0, 1); printf("%d\n", min);}// 2）两个数组，长度分别为N，都有序，找到两个数组中，第N小的数字。// 例如[1 2 3 4 6] [5 7 8 9 10],那么5是正确的答案。写出代码int bisectwo(int A[], int B[], int na, int nb, int k) { int lowera = 0, lowerb = 0, mida, midb; int uppera = na > k ? k - 1: na - 1; int upperb = nb > k ? k - 1: nb - 1; while (uppera >= lowera && upperb >= lowerb) { mida = lowera + (uppera - lowera) / 2; midb = lowerb + (upperb - lowerb) / 2; if (A[mida] > B[midb]) { if (k < mida - lowera + midb - lowerb + 2) { uppera = mida - 1; } else { k -= midb - lowerb + 1; lowerb = midb + 1; } } else { if (k < mida - lowera + midb - lowerb + 2) { upperb = midb - 1; } else { k -= mida - lowera + 1; lowera = mida + 1; } } } if (lowera > uppera) { return B[lowerb + k - 1]; } if (lowerb > upperb) { return A[lowera + k - 1]; }}void test_bisectwo() { int i, kth; int A[][5] = { {1, 2, 3, 4, 6}, {1, 2, 3, 4, 6}, {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {1, 1, 1, 1, 1} }; int B[][5] = { {5, 7, 8, 9, 10}, {1, 2, 3, 4, 6}, {6, 7, 8, 9, 10}, {1, 2, 3, 4, 5}, {2, 2, 2, 2, 2} }; int A0[] = {1}; int B0[] = {2}; printf("test_bisectwo\n"); for (i = 0; i < 5; i++) { kth = bisectwo(A[i], B[i], 5, 5, 5); printf("%d\n", kth); } kth = bisectwo(A0, B0, 1, 1, 2); printf("%d\n", kth);}void swap(int *a, int *b) { int c; c = *a; *a = *b; *b = c; // printf("a %d b %d\n", *a, *b);}void print_list(int list[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", list[i]); printf("\n");}// 3）一个数组长度为N，找出其中K个最大的数字。写出代码。int *klargest(int list[], int n, int k) { int i, last; if (n == k) return list+n; last = 0; for (i = 1; i < n; i++) if (list[i] > list[0]) swap(&list[++last], &list[i]); swap(&list[last], &list[0]); if (k <= last + 1) return klargest(list, last+1, k); else return klargest(list+last+1, n-last-1, k-last-1);}void test_klargest() { int list[][5] = { {1, 2, 3, 4, 5}, {2, 4, 3, 5, 1}, {1, 2, 5, 4, 3}, {5, 4, 3, 2, 1}, {1, 1, 2, 2, 2}, {1, 1, 1, 1, 1} }; int list0[] = {1}; int i, *p, *k; printf("test_klargest\n"); for (i = 0; i < 6; i++) { k = klargest(list[i], 5, 4); for (p = list[i]; p != k; p++) printf("%d ", *p); printf("\n"); } k = klargest(list0, 1, 1); for (p = list0; p != k; p++) printf("%d ", *p); printf("\n");}int main() { test_bisecmin(); test_bisectwo(); test_klargest(); return 0;}
[解决办法]
第一问看起来容易 只要二分 但是要过掉 {2, 2, 1, 1, 2, 2} 这样的数据还要比较细心才行
第二问也还是 divide and conquer
第三问就是模范quick sort了
下面是代码 不过很tricky的数据没有试过
#include <stdio.h>// 1）一个数组，长度为N，为循环有序的。找出其中的最小值// 所谓循环有序就是 [ 4 5 6 1 2 3] 这种，1是我们要找的。// 时间复杂度你们肯定比我清楚。写出代码int bisecmin(int list[], int n) { int lower = 0, upper = n - 1, mid; if (list[upper] > list[lower]) return list[lower]; do { mid = lower + (upper - lower) / 2; if (list[lower] <= list[mid]) lower = mid + 1; else upper = mid; } while (list[lower] > list[upper]); return list[lower];}void test_bisecmin() { int i, min; int list[][6] = { {1, 2, 3, 4, 5, 6}, {2, 3, 4, 5, 6, 1}, {3, 4, 5, 6, 1, 2}, {4, 5, 6, 1, 2, 3}, {5, 6, 1, 2, 3, 4}, {6, 1, 2, 3, 4, 5}, {1, 1, 1, 1, 1, 1}, {2, 2, 1, 1, 2, 2} }; int list0[] = {1}; printf("test_bisecmin\n"); for (i = 0; i < 8; i++) { min = bisecmin(list[i], 6); printf("%d\n", min); } min = bisecmin(list0, 1); printf("%d\n", min);}// 2）两个数组，长度分别为N，都有序，找到两个数组中，第N小的数字。// 例如[1 2 3 4 6] [5 7 8 9 10],那么5是正确的答案。写出代码int bisectwo(int A[], int B[], int na, int nb, int k) { int lowera = 0, lowerb = 0, mida, midb; int uppera = na > k ? k - 1: na - 1; int upperb = nb > k ? k - 1: nb - 1; while (uppera >= lowera && upperb >= lowerb) { mida = lowera + (uppera - lowera) / 2; midb = lowerb + (upperb - lowerb) / 2; if (A[mida] > B[midb]) { if (k < mida - lowera + midb - lowerb + 2) { uppera = mida - 1; } else { k -= midb - lowerb + 1; lowerb = midb + 1; } } else { if (k < mida - lowera + midb - lowerb + 2) { upperb = midb - 1; } else { k -= mida - lowera + 1; lowera = mida + 1; } } } if (lowera > uppera) { return B[lowerb + k - 1]; } if (lowerb > upperb) { return A[lowera + k - 1]; }}void test_bisectwo() { int i, kth; int A[][5] = { {1, 2, 3, 4, 6}, {1, 2, 3, 4, 6}, {1, 2, 3, 4, 5}, {6, 7, 8, 9, 10}, {1, 1, 1, 1, 1} }; int B[][5] = { {5, 7, 8, 9, 10}, {1, 2, 3, 4, 6}, {6, 7, 8, 9, 10}, {1, 2, 3, 4, 5}, {2, 2, 2, 2, 2} }; int A0[] = {1}; int B0[] = {2}; printf("test_bisectwo\n"); for (i = 0; i < 5; i++) { kth = bisectwo(A[i], B[i], 5, 5, 5); printf("%d\n", kth); } kth = bisectwo(A0, B0, 1, 1, 2); printf("%d\n", kth);}void swap(int *a, int *b) { int c; c = *a; *a = *b; *b = c; // printf("a %d b %d\n", *a, *b);}void print_list(int list[], int n) { int i; for (i = 0; i < n; i++) printf("%d ", list[i]); printf("\n");}// 3）一个数组长度为N，找出其中K个最大的数字。写出代码。int *klargest(int list[], int n, int k) { int i, last; if (n == k) return list+n; last = 0; for (i = 1; i < n; i++) if (list[i] > list[0]) swap(&list[++last], &list[i]); swap(&list[last], &list[0]); if (k <= last + 1) return klargest(list, last+1, k); else return klargest(list+last+1, n-last-1, k-last-1);}void test_klargest() { int list[][5] = { {1, 2, 3, 4, 5}, {2, 4, 3, 5, 1}, {1, 2, 5, 4, 3}, {5, 4, 3, 2, 1}, {1, 1, 2, 2, 2}, {1, 1, 1, 1, 1} }; int list0[] = {1}; int i, *p, *k; printf("test_klargest\n"); for (i = 0; i < 6; i++) { k = klargest(list[i], 5, 4); for (p = list[i]; p != k; p++) printf("%d ", *p); printf("\n"); } k = klargest(list0, 1, 1); for (p = list0; p != k; p++) printf("%d ", *p); printf("\n");}int main() { test_bisecmin(); test_bisectwo(); test_klargest(); return 0;}
[解决办法]
第一题
循环有序的定义
对于长度为N的数组a，存在一个整数t，0 <= t <= N，定义新的数组b
{a[(t + 0) mod N], a[(t + 1) mod N], a[(t + 2) mod N], ……, a[( t + N - 1) mode N]}
若数组b是有序的，则称数组a是循环有序的。
算法
假设数组a是循环有序递增的，现在需要找到这个数组中的最小值。
对数组a任取一子数组，如果这个子数组的第一个元素小于最后一个元素，则这个子数组是有序递增的。
将数组a分为两个子数组，如果这两个子数组都是有序递增的，那么比较两个数组的第一个元素，较小者为此数组的最小值。
如果有一个数组不是有序递增的，那么最小是肯定位于这个子数组内。然后对这个子数组再进行查找。
采用分治递归的方法来计算这个最小值。
Find_Minimum(A, p, q)
t = (p + q) / 2
// 两个子数组都是严格有序的
if ((A(p) <= A(t)) && (A(t + 1) <= A(q)))
return min(A(p), A(t+1));
else if (A(p) > A(t))
return Find_Minimum(A, p, t);
else
return Find_Minimum(A, t + 1, q);
代码的话是这样的
#include <iostream>using namespace std;int min_u(int a, int b){ if (a < b) { return a; } else { return b; }}int findMinimum(int * dataArray, int begin, int end){ int middle = (begin + end) / 2; if ((dataArray[begin] <= dataArray[middle]) && (dataArray[middle + 1] <= dataArray[end])) { return min_u(dataArray[begin], dataArray[middle + 1]); } else if (dataArray[begin] > dataArray[middle]) { return findMinimum(dataArray, begin, middle); } else { return findMinimum(dataArray, middle + 1, end); }}int main(){ int dataArray[] = {4, 5, 6, 7, 9, 10 ,15 ,47, 1, 2, 3}; int minimum = findMinimum(dataArray, 0, 11); cout << minimum << endl; return 0;}
[解决办法]
重造轮子的部分
代码来自SGI STL，我只有稍作修改，费了好大的劲才搞懂
template<typename RandomItr, typename Distance, typename T, typename BiFunc>void push_heap_implement(RandomItr first, Distance hole_index, Distance top_index, T value, BiFunc const &func);template<typename RandomItr, typename Distance, typename T, typename BiFunc>void adjust_heap(RandomItr first, Distance hole_index, Distance len, T value, BiFunc const &func){ Distance top_index = hole_index; Distance first_child = 2 * hole_index + 1; Distance second_child = first_child + 1; while(second_child < len) { if( func(*(first + second_child), *(first + first_child)) ) --second_child; *(first + hole_index) = *(first + second_child); hole_index = second_child; second_child = 2 * hole_index + 2; } if(second_child == len) { *(first + hole_index) = *(first + (second_child - 1)); hole_index = second_child - 1; } push_heap_implement(first, hole_index, top_index, value, func);}template<typename RandomItr, typename BiFunc>void pop_heap_2(RandomItr first, RandomItr last, BiFunc const &){ typedef typename std::iterator_traits<RandomItr>::difference_type difference_type; RandomItr result = last - 1; *result = *first; adjust_heap(first, difference_type(0), difference_type(last - first - 1), *result, BiFunc() );}template<typename RandomItr, typename Distance, typename T, typename BiFunc>void push_heap_implement(RandomItr first, Distance hole_index, Distance top_index, T value, BiFunc const &func){ Distance parent = (hole_index - 1) / 2; while(hole_index > top_index && func(*(first + parent), value) ) { *(first + hole_index) = *(first + parent); hole_index = parent; parent = (hole_index - 1) / 2; } *(first + hole_index) = value;}template<typename RandomItr, typename BiFunctor>void push_heap_2(RandomItr first, RandomItr last, BiFunctor const &func){ typedef typename std::iterator_traits<RandomItr>::difference_type difference_type; typename std::iterator_traits<RandomItr>::value_type value = *(last - 1); push_heap_implement(first, difference_type(last - first - 1), difference_type(0), value, BiFunctor() );}template<typename RandomItr, typename BiFunc>void make_heap_2(RandomItr first, RandomItr last, BiFunc const &func){ if(last - first < 2) return; typedef typename std::iterator_traits<RandomItr>::difference_type difference_type; typedef typename std::iterator_traits<RandomItr>::value_type value_type; difference_type len = last - first; difference_type hole_index = (len - 2) / 2; while(true) { adjust_heap(first, hole_index, len, value_type(*(first + hole_index) ), func); if(hole_index == 0) return; --hole_index; }}
[解决办法]
补上代码，似乎无法显示
实际执行的部分
template<typename ForwardItr>std::vector<typename std::iterator_traits<ForwardItr>::value_type> constnth_max(ForwardItr first, ForwardItr last, size_t number){ if(first == last) return std::vector<int>(); if(static_cast<size_t>(std::distance(first, last)) < number ) return std::vector<int>(); typedef typename std::iterator_traits<ForwardItr>::value_type value_type; std::vector<value_type> heap(first, first + number); make_heap_2(std::begin(heap), std::end(heap), std::greater<value_type>() ); std::advance(first, number); while(first != last) { if(heap[0] < *first) { pop_heap_2(std::begin(heap), std::end(heap), std::greater<value_type>() ); heap.pop_back(); heap.push_back(*first); push_heap_2(std::begin(heap), std::end(heap), std::greater<value_type>() ); } ++first; } return heap;}inline void sort_three_01(){ std::vector<int> array_1= {77, 88, 0, 4, 4 ,5 ,6 ,1 ,2 ,3, 9, 10, 20}; std::vector<int> result = nth_max(std::begin(array_1), std::end(array_1), 2); for(int const data : result) std::cout << data << std::endl;}
[解决办法]
第一题：没思路，最坏情况下O(N)的时间复杂度貌似没法避免，老老实实用std::min_element吧。
第二题：合并排序中的合并算法，但只要合并到前N个元素就可以了，STL中没有现成的，只能手写代码。
#include <iostream>int min_nth(const int *array1, const int *array2, size_t N){ size_t merged_count = 0; while(true) { if(*array1 < *array2) { if(++merged_count == N) { return *array1; } else { array1++; } } else { if(++merged_count == N) { return *array2; } else { array2++; } } }}int main(){ using namespace std; int array1[] = { 3, 4, 5, 6, 7 }; int array2[] = { 1, 2, 3, 4, 5 }; cout << min_nth(array1, array2, 5) << endl; return 0;}
[解决办法]