華為面試編程題詳解.-.1(整理)

来源:互联网 时间:1970-01-01

 1 /* 2 题目如下:
3 有1,2,....一直到n的无序数组,求排序算法,要求时间复杂度为O(n), 空间复杂度为O(1)。使用交换,而且一次只能交换两个数。
4 解题思路:
5 因为从1,2......n刚好需要一个数组a[n],排序后,a[i]=i+i; 所以就出現了,a[a[i]-1] = a[i]; 最终完成以后,i的位置上放值得数据值会是i+1问题的关键在于数组的值是1到n,否则是不可能在时间复杂度为O(n),空间复杂度为O(1)内完成的
6 */
7
8 #include <iostream.h>
9 #include <assert.h>
10 #include <string.h>
11
12 void main(void)
13 {
14 int a[] = {2, 4, 1, 3};
15 int len = sizeof(a)/sizeof(a[0]);
16 int temp;
17 for (int i = 0; i < len; ++i)
18 {
19 temp = a[a[i] - 1];
20 a[a[i] - 1] = a[i];
21 a[i] = temp;
22 if(a[i] == i+1) //預先判斷下次元素是否符合應該放置的位子
23 i++;
24 }
25 for (int j=0; j < len; j++)
26 {
27 cout<<a[j]<<" ";
28 }
29 cout<<endl;
30 }


相关阅读:
Top