2013-09-02 16:28:35
找出数字在排序数组中出现的次数。
注意几点:
- 一开始试图用size_t类型表示数组的下标begin、end,到那时这样做在end = 0时,end - 1是size_t类型的最大值,仍然满足begin <= end,但此时将会对sortedArray数组中下标为size_t类型的最大值的元素,会出现访问越界;因此,对于数组小标,不要为了保证是整数二用size_t类型,用int类型比较好。
- 若用int型表示,就不需要用STATUS的状态标志,下面的程序中没有修改这一点。
代码:
1 #include <iostream> 2 #include <cassert> 3 using namespace std; 4 5 typedef int DataType; 6 7 const bool SuccessToFind = true; 8 const bool FailToFind = false; 9 10 bool STATUS = SuccessToFind; 11 12 //找出第一个K出现的位置的下标 13 int GetFirstK(DataType *sortedArray,int begin,int end,const DataType data) 14 { 15 /*assert(NULL != sortedArray); 16 assert(begin <= end);*/ 17 18 STATUS = FailToFind; 19 int mid = 0; 20 21 while (begin <= end) 22 { 23 mid = begin + (end - begin) / 2; 24 if (sortedArray[mid] == data) 25 { 26 if (mid == begin || sortedArray[mid - 1] != data) 27 { 28 STATUS = SuccessToFind; 29 return mid; 30 } 31 else 32 { 33 end = mid - 1; 34 } 35 } 36 else if (sortedArray[mid] < data) 37 { 38 begin = mid + 1; 39 } 40 else 41 { 42 end = mid - 1; //mid为0时,若end为size_t类型,会出错 43 } 44 } 45 46 STATUS = FailToFind; 47 return 0; 48 } 49 50 //找出最后一个K出现的位置的下标 51 int GetLastK(DataType *sortedArray,int begin,int end,const DataType data) 52 { 53 /*assert(NULL != sortedArray); 54 assert(begin <= end);*/ 55 56 STATUS = FailToFind; 57 int mid = 0; 58 59 while (begin <= end) 60 { 61 mid = begin + (end - begin) / 2; 62 if (sortedArray[mid] == data) 63 { 64 if (mid == end || sortedArray[mid + 1] != data) 65 { 66 STATUS = SuccessToFind; 67 return mid; 68 } 69 else 70 { 71 begin = mid + 1; 72 } 73 } 74 else if (sortedArray[mid] < data) 75 { 76 begin = mid + 1; 77 } 78 else 79 { 80 end = mid - 1; 81 } 82 } 83 84 STATUS = FailToFind; 85 return 0; 86 } 87 88 //返回K出现的次数 89 int GetNumberOfK(DataType *sortedArray,int len,const DataType data) 90 { 91 assert(NULL != sortedArray); 92 assert(len >= 1); 93 94 size_t begin = GetFirstK(sortedArray,0,len - 1,data); 95 size_t end = GetLastK(sortedArray,0,len - 1,data); 96 97 if (STATUS == SuccessToFind) 98 { 99 return (end - begin + 1); 100 } 101 else 102 { 103 return 0; 104 } 105 } 106 107 //测试GetNumberOfK 108 void TestGetNumberOfK() 109 { 110 DataType sortedArray[10] = {1,2,3,3, 3,3,4,4, 5,6}; 111 size_t len = 10; 112 DataType data = 0; 113 114 cout<<"please enter the data to find ,end with ctrl+z "<<endl; 115 while (cin>>data) 116 { 117 cout<<"the number of "<<data<<" in array is : "<<GetNumberOfK(sortedArray,len,data)<<endl; 118 cout<<"please enter the data to find ,end with ctrl+z "<<endl; 119 } 120 121 } 122 123 int main() 124 { 125 TestGetNumberOfK(); 126 return 0; 127 }
测试结果:
please enter the data to find ,end with ctrl+z 3 the number of 3 in array is : 4 please enter the data to find ,end with ctrl+z 4 the number of 4 in array is : 2 please enter the data to find ,end with ctrl+z 2 the number of 2 in array is : 1 please enter the data to find ,end with ctrl+z 1 the number of 1 in array is : 1 please enter the data to find ,end with ctrl+z -1 the number of -1 in array is : 0 please enter the data to find ,end with ctrl+z 90 the number of 90 in array is : 0 please enter the data to find ,end with ctrl+z ^Z 请按任意键继续. . .