安全的赣州网站建设,自适应网站建设,贵州碧江区住房和城乡建设局网站,招聘网站做招聘顾问2014-03-21 22:23 题目#xff1a;假设你一开始有一个空数组#xff0c;你在读入一些整数并将其插入到数组中#xff0c;保证插入之后数组一直按升序排列。在读入的过程中#xff0c;你还可以进行一种操作#xff1a;查询某个值val是否存在于数组中#xff0c;并给出这个… 2014-03-21 22:23 题目假设你一开始有一个空数组你在读入一些整数并将其插入到数组中保证插入之后数组一直按升序排列。在读入的过程中你还可以进行一种操作查询某个值val是否存在于数组中并给出这个元素在数组中的位置(如果有多个的重复元素话给出最小的下标)。 解法书上的原题不是这么描述的但我觉得用这种插入排序的说法更好理解。虽然说是数组但实际上既可以用真的数组来模拟这一过程也可以用一棵二叉搜索树来做。我的实现是用二叉搜索树每个节点里除了记录元素的值之外还记录它的左子树有多少个点。这样在树里面也能进行对数级的查找。其实用数组直接模拟的话代码应该更好写的。 代码 1 // 11.8 Given an array of integers, find out for a given value, how many integers are there in the array, that are no greater than the value.2 // If the value is not in the array, return -1 instead.3 #include algorithm4 #include iostream5 #include string6 using namespace std;7 8 struct TreeNode {9 int val;
10 int count;
11 int count_left;
12 TreeNode *left;
13 TreeNode *right;
14 TreeNode(int _val 0): val(_val), count(1), count_left(0), left(nullptr), right(nullptr) {};
15 };
16
17 void insertNode(TreeNode *root, int val)
18 {
19 if (root nullptr) {
20 root new TreeNode(val);
21 } else if (val root-val) {
22 (root-count);
23 } else if (val root-val) {
24 (root-count_left);
25 insertNode(root-left, val);
26 } else {
27 insertNode(root-right, val);
28 }
29 }
30
31 int getRank(TreeNode *root, int val)
32 {
33 int result;
34 TreeNode *ptr;
35
36 result 0;
37 ptr root;
38 while (ptr ! nullptr) {
39 if (ptr-val val) {
40 ptr ptr-left;
41 } else if (ptr-val val) {
42 result ptr-count_left 1;
43 ptr ptr-right;
44 } else {
45 break;
46 }
47 }
48 if (ptr ! nullptr) {
49 result ptr-count_left;
50 return result;
51 } else {
52 return -1;
53 }
54 }
55
56 void clearTree(TreeNode *root)
57 {
58 if (root ! nullptr) {
59 clearTree(root-left);
60 clearTree(root-right);
61 delete root;
62 root nullptr;
63 }
64 }
65
66 int main()
67 {
68 int val;
69 TreeNode *root;
70 string s;
71
72 root nullptr;
73 while (cin s) {
74 if (s i) {
75 cin val;
76 insertNode(root, val);
77 } else if (s r) {
78 cin val;
79 printf(rank %d\n, getRank(root, val));
80 } else if (s e) {
81 break;
82 }
83 }
84 clearTree(root);
85
86 return 0;
87 } 转载于:https://www.cnblogs.com/zhuli19901106/p/3616871.html
