一个关于数组的问题
一个数组 {5, 2, 9, 4, 7}
这个数组有 5 个元素
这 5 个元素的位置依次是 1 2 3 4 5
这 5 个元素的从小到大的顺序是 3 1 5 2 4
数组中的一个元素，有三个属性即：
元素本身 A 5 2 9 4 7
原来在数组中的位置 B 1 2 3 4 5
从小到大的顺序 C 3 1 5 2 4
给定一个数组，如何得到每个元素的这三个属性？
对于每个元素，知道其中一个属性，如何得到另外两个属性
B 和 C 都是从 1 到 5 的。
对 B 可以排个序，然后按索引取即可。
C 也是如此。
对于 A ，因为其是有间隔的，如果直接按索引，可能会浪费空间。可以采用哈希去做 O(1) 。
也可以直接对其进行一遍扫描 O(N) 。
或者建立平衡二叉树 O(logN) 。
1 #include <iostream>
2 #include <cstdlib>
3 using namespace std;
4
5 struct Element
6 {
7 int value;
8 int position;
9 int order;
10 };
11
12 int cmpByValue(const void* a, const void* b)
13 {
14 return ((Element*)a)->value - ((Element*)b)->value;
15 }
16
17 int cmpByPosition(const void* a, const void* b)
18 {
19 return ((Element*)a)->position - ((Element*)b)->position;
20 }
21
22 int cmpByOrder(const void* a, const void* b)
23 {
24 return ((Element*)a)->order - ((Element*)b)->order;
25 }
26
27 int main()
28 {
29 int a[] = {5, 2, 9, 4, 7};
30 Element els[5];
31 for (int i = 0; i != 5; ++i)
32 {
33 els[i].value = a[i];
34 els[i].position = i + 1;
35 }
36 qsort(els, 5, sizeof (*els), cmpByValue);
37
38 for (int i = 0; i != 5; ++i)
39 {
40 els[i].order = i + 1;
41 }
42
43 for (int i = 0; i != 5; ++i)
44 {
45 cout << els[i].value << ' ' << els[i].position << ' ' << els[i].order << endl;
46 }
47 cout << endl;
48
49 qsort(els, 5, sizeof (*els), cmpByPosition);
50
51 for (int i = 0; i != 5; ++i)
52 {
53 cout << els[i].value << ' ' << els[i].position << ' ' << els[i].order << endl;
54 }
55 cout << endl;
56
57 qsort(els, 5, sizeof (*els), cmpByOrder);
58 for (int i = 0; i != 5; ++i)
59 {
60 cout << els[i].value << ' ' << els[i].position << ' ' << els[i].order << endl;
61 }
62
63 return 0;
64 }
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/http://www.slyar.com/blog/stdlib-qsort.htmlhttp://www.cppblog.com/qywyh/articles/3405.htmlhttp://pubs.opengroup.org/onlinepubs/009695399/functions/qsort.htmlhttp://linux.die.net/man/3/qsorthttp://en.wikipedia.org/wiki/Qsorthttp://msdn.microsoft.com/en-us/library/aa272872(v=vs.60).aspx
posted on 2011-07-20 11:32
unixfy 阅读(97)
评论(0) 编辑 收藏 引用