昨天面试的一道上机笔试题,哪位朋友有好的思路吗?

flfq

肯定是个学汇编出身的，连下标都讲出来了

pitonas

挺不错的了，支持。

bruceteen

回复 11# BuTa丶潇
用equal_range的话，我写个demo
如果你的编译器支持最新的C++标准，那么

1. #include <vector>
   
2. #include <algorithm>
   
3. #include <iostream>
   
4. using namespace std;
   
5. 
   
6. void foo( const double* buf, size_t n, double a, double b )
   
7. {
   
8.     std::pair<const double*,const double*> range = std::equal_range( buf+0, buf+n, a
   
9.         , [a,b](double e1, double e2) {
   
10.             int v1 = e1<a ? -1 : ( e1<=b ? 0 : 1 );
    
11.             int v2 = e2<a ? -1 : ( e2<=b ? 0 : 1 );
    
12.             return v1 < v2;
    
13.         } );
    
14. 
    
15.     if( range.first == range.second )
    
16.     {
    
17.         std::cout << "不存在" << std::endl;
    
18.         return;
    
19.     }
    
20. 
    
21.     std::cout << (range.first-buf) << " - " << (range.second-buf-1) << std::endl;
    
22. }
    
23. 
    
24. template<size_t N>
    
25. inline void foo( const double (&buf)[N], double a, double b )
    
26. {
    
27.     foo( buf, N, a, b );
    
28. }
    
29. 
    
30. int main()
    
31. {
    
32.     double buf[] = { 3 , 3.5 , 5.7 , 6.8 , 11 , 15.4 };
    
33. 
    
34.     foo( buf, 0.3, 10 ); // 0-3
    
35.     foo( buf, 1, 2 ); //
    
36.     foo( buf, 19.4, 22 ); //
    
37.     foo( buf, 3.5, 17 ); // 1-5
    
38. 
    
39.     return 0;
    
40. }
    

复制代码

如果你的编译器比较老旧，用

1. #include <vector>
   
2. #include <algorithm>
   
3. #include <iostream>
   
4. using namespace std;
   
5. 
   
6. struct ablesser_
   
7. {
   
8.     ablesser_( double a, double b ) : a_(a), b_(b)
   
9.     {
   
10.     }
    
11. 
    
12.     bool operator()( double e1, double e2 ) const
    
13.     {
    
14.         int v1 = e1<a_ ? -1 : ( e1<=b_ ? 0 : 1 );
    
15.         int v2 = e2<a_ ? -1 : ( e2<=b_ ? 0 : 1 );
    
16.         return v1 < v2;
    
17.     }
    
18. 
    
19.     double a_, b_;
    
20. };
    
21. 
    
22. void foo( const double* buf, size_t n, double a, double b )
    
23. {
    
24.     std::pair<const double*,const double*> range = std::equal_range( buf+0, buf+n, a, ablesser_(a,b) );
    
25. 
    
26.     if( range.first == range.second )
    
27.     {
    
28.         std::cout << "不存在" << std::endl;
    
29.         return;
    
30.     }
    
31. 
    
32.     std::cout << (range.first-buf) << " - " << (range.second-buf-1) << std::endl;
    
33. }
    
34. 
    
35. template<size_t N>
    
36. inline void foo( const double (&buf)[N], double a, double b )
    
37. {
    
38.     foo( buf, N, a, b );
    
39. }
    
40. 
    
41. int main()
    
42. {
    
43.     double buf[] = { 3 , 3.5 , 5.7 , 6.8 , 11 , 15.4 };
    
44. 
    
45.     foo( buf, 0.3, 10 ); // 0-3
    
46.     foo( buf, 1, 2 ); //
    
47.     foo( buf, 19.4, 22 ); //
    
48.     foo( buf, 3.5, 17 ); // 1-5
    
49. 
    
50.     return 0;
    
51. }
    

复制代码

当然，代码都有些晦涩，最佳的办法应该是调用 std::lower_bound 获得第一个下标，std::upper_bound  获得第二个下标（其实你要的是这个值之前一位置）

BuTa丶潇

回复 23# bruceteen


    十分感谢!!{:3_193:}

我在你的基础上,也尝试了下代码:

1. 
   
2. #include<iostream>
   
3. #include <vector>
   
4. using namespace std;
   
5. /*找出满足这个区间的数据在数组里面的下标*/
   
6. void range(vector<double> &nums,const double & a,const double & b){
   
7.         if( b < *nums.begin() || a > nums.back() ) {
   
8.                 cout <<"a=" << a << ",b=" << b << " , no fits!"<< endl;
   
9.                 exit(0);
   
10.         } else {
    
11.                 pair<vector<double>::iterator,vector<double>::iterator> range_a , range_b ;
    
12.                 range_a = equal_range(nums.begin(),nums.end(),a);
    
13.                 range_b = equal_range(nums.begin(),nums.end(),b);
    
14.                 cout<<range_a.first-nums.begin()<<'-'<<range_b.second-nums.begin()-1<<endl;
    
15.         }//得到a,b的查找位置.
    
16. }
    
17. int main(void) {
    
18.         double array[4]={1.5,2.6,2.6,3.7};//测试数据
    
19.         vector<double> nums;
    
20.         for(int i=0;i<3;i++)
    
21.                 nums.push_back(array[i]);
    
22.         range (nums,   0, 3.2);//a=0,b=3.2 测试区间[0,3.2]        res->0-1
    
23.         range (nums, 5.3, 9.2);//测试区间[5.3,9.2]                        res->none
    
24.         return 0;
    
25. }
    

复制代码

总之学到了很多东西..再次感谢!!

bruceteen

回复 24# BuTa丶潇
这……，我用lower_bound/upper_bound重写吧

若你的编译器支持C++11标准

1. #include <vector>
   
2. #include <algorithm>
   
3. #include <iostream>
   
4. 
   
5. void range( const std::vector<double>& buf, double a, double b )
   
6. {
   
7.     auto p1 = std::lower_bound( buf.begin(), buf.end(), a );
   
8.     auto p2 = std::upper_bound( buf.begin(), buf.end(), b );
   
9. 
   
10.     if( p1 == p2 )
    
11.         std::cout << "a=" << a << ", b=" << b << ", no fits!" << std::endl;
    
12.     else
    
13.         std::cout << std::distance(buf.begin(),p1) << '-' << std::distance(buf.begin(),p2)-1 << std::endl;
    
14. }
    
15. 
    
16. using namespace std;
    
17. 
    
18. int main()
    
19. {
    
20.     vector<double> nums = { 1.5, 2.6, 2.6, 3.7 };//测试数据
    
21.     range( nums,   0, 3.2 ); // 0-2
    
22.     range( nums, 5.3, 9.2 ); // no fits
    
23. 
    
24.     return 0;
    
25. }
    

复制代码

若你的编译器不支持C++11标准

1. #include <vector>
   
2. #include <algorithm>
   
3. #include <iostream>
   
4. 
   
5. void range( const std::vector<double>& buf, double a, double b )
   
6. {
   
7.     std::vector<double>::const_iterator p1 = std::lower_bound( buf.begin(), buf.end(), a );
   
8.     std::vector<double>::const_iterator p2 = std::upper_bound( buf.begin(), buf.end(), b );
   
9. 
   
10.     if( p1 == p2 )
    
11.         std::cout << "a=" << a << ", b=" << b << ", no fits!" << std::endl;
    
12.     else
    
13.         std::cout << std::distance(buf.begin(),p1) << '-' << std::distance(buf.begin(),p2)-1 << std::endl;
    
14. }
    
15. 
    
16. using namespace std;
    
17. 
    
18. int main()
    
19. {
    
20.     vector<double> nums;
    
21.     {
    
22.         const double array[] = { 1.5, 2.6, 2.6, 3.7 }; // 测试数据
    
23.         const size_t len = sizeof(array)/sizeof(array[0]);
    
24.         nums.reserve( len );
    
25.         for( size_t i=0; i<len; ++i )
    
26.             nums.push_back( array[i] );
    
27.     }
    
28.     range( nums,   0, 3.2 ); // 0-2
    
29.     range( nums, 5.3, 9.2 ); // no fits
    
30. 
    
31.     return 0;
    
32. }
    

复制代码

lanlill

创建结构体，struct data {int   cnt，double data_value}
存储原数组下标与值  耗时n
遍历原数组，取值大于后等于a的最接近值x，小于或等于b的最接近值y  耗时2n
qsort  struct data    对数级
bsearch struct data   x对数级
bsearch struct data   y对数级
取出  x,y之间的所有data.cnt  n
耗时5n左右

手眼通天

3楼正解

leejqy

如果只有几个[a, b]需要输出，直接for(i=0;i<n;++i)if()else 复杂度O(k*n)
如果[a, b]较多，排序+二分，复杂度O(k * nlogn)