程序员面试真题--（1）

题目描述：

使用O（1）的空间复杂度交换数组的左右两个子数组

思路：

类似于字符串循环移位，xy->xtyt->(xtyt)t

 1 #include <iostream>
 2 #include <queue>
 3 #include <climits>
 4 #include <algorithm>
 5 #include <memory.h>
 6 #include <stdio.h>
 7 #include <map>
 8 using namespace std;
 9 
10 template<typename T>
11 void swap_arr(vector<T> &arr,int s,int e)
12 {
13     T tmp;
14     while(s <= e)
15     {
16         tmp = arr[s];
17         arr[s] = arr[e];
18         arr[e] = tmp;
19         s++;
20         e--;
21     }
22     return;
23 }
24 
25 template<typename T>
26 void fun(vector<T> &arr,int k)
27 {
28     if(arr.size() <= 0)
29         return
30     swap_arr(arr,0,k);
31     swap_arr(arr,k+1,arr.size()-1);
32     swap_arr(arr,0,arr.size()-1);
33 }
34 
35 int main()
36 {
37     vector<int> a;
38     a.push_back(1);
39     a.push_back(3);
40     a.push_back(4);
41     a.push_back(5);
42     fun(a,1);
43     vector<int>::iterator ite=a.begin();
44     while(ite != a.end())
45     {
46         cout<<*ite<<endl;
47         ++ite;
48     }
49     return 0;
50 }