一個關于數組的問題
一個數組 {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://m.shnenglu.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 閱讀(89)
評論(0) 編輯 收藏 引用