动态规划——主元素算法

Q : 何为主元素：

设T[0:n-1]是n个元素的数组，对任意一个元素x，设S(x) = { i | T[i] = x }。当| S(x) | > n/2 时，称x为T的主元素。

算法实现：

1、快排 + 判断中位数

2、分治思想 (分解、递归实现)

3、线性算法 (主元素个数大于n/2)

方法一：针对有序数组，若存在主元素，则主元素肯定是中位数。

思路：先对数组进行快速排序，然后求解有序数组的中位数，若中位数个数>n/2 (或者判断中位数与第一个、最后一个元素的关系)，则中位数为主元素，否则不存在主元素。

分析：时间复杂度为O（nlogn）

  1 #include <stdio.h>
  2 
  3 #include <windows.h>
  4 
  5  
  6 
  7 //利用快速排序的方法求中位数
  8 
  9 void swap(int *a, int *b)
 10 
 11 {
 12 
 13         int temp = 0;
 14 
 15         temp = *a; 
 16 
 17         *a = *b;
 18 
 19         *b = temp;
 20 
 21 }
 22 
 23  
 24 
 25 int partition(int *num, int start, int end)
 26 
 27 {
 28 
 29         int x = num[end];
 30 
 31         int i = start-1;
 32 
 33         int j;
 34 
 35         for (j = start; j < end; j++) {
 36 
 37                 if (num[j] <= x) {
 38 
 39                         i = i + 1;
 40 
 41                         swap(&num[i], &num[j]);
 42 
 43                 }
 44 
 45         }
 46 
 47         swap(&num[i+1], &num[end]);
 48 
 49         return i+1;
 50 
 51 }
 52 
 53  
 54 
 55 void quicksort(int *num, int start, int end)
 56 
 57 {
 58 
 59         if( start < end) {
 60 
 61                 int mid = partition(num, start, end);
 62 
 63                 quicksort(num, start, mid-1);
 64 
 65                 quicksort(num, mid+1, end);
 66 
 67         }
 68 
 69 }
 70 
 71  
 72 
 73 int main()
 74 
 75 {
 76 
 77         int i,n;
 78 
 79 int num[10];
 80 
 81 int index;
 82 
 83 printf("please input the number of a[]:");
 84 
 85 scanf("%d",&n);
 86 
 87 printf("please input a[]:
");
 88 
 89 for(i=0;i<n;i++)
 90 
 91 scanf("%d",&num[i]);
 92 
 93         quicksort(num, 0, n-1);
 94 
 95         for (i = 0; i < n; i++) {
 96 
 97                 printf("%d
", num[i]);
 98 
 99         }
100 
101 if(n%2 == 0)
102 
103 index=n/2-1;
104 
105         else 
106 
107 index = n/2; //奇数n/2偶数n/2-1
108 
109 //中位数与第一个或者最后一个数相同，则为主元素
110 
111         if (num[0] == num[index] || num[n-1] == num[index]) {
112 
113                 printf("main element exits: index = %d element = %d
", index, num[index]);
114 
115         }
116 
117         else {
118 
119                 printf("main element not exits
");
120 
121         }
122 
123 Sleep(10000000);
124 
125 }

代码实现

方法二：分治法

思路：若T 中存在主元素，则将T 分为两部分后，T 的主元素也必为两部分中至少一部分的主元素，因此可用分治法。

将元素划分为两部分，递归地检查两部分有无主元素。具体算法如下：

a. 若T 只含一个元素，则此元素就是主元素，返回此数。

b. 将T 分为两部分T1 和T2（二者元素个数相等或只差一个），分别递归调用此方法求其主元素m1 和m2。

c. 若m1 和m2 都存在且相等，则这个数就是T 的主元素，返回此数。

d. 若m1 和m2 都存在且不等，则分别检查这两个数是否为T 的主元素，若有则返回此数，若无则返回空值。

e. 若m1 和m2 只有一个存在，则检查这个数是否为T 的主元素，若是则返回此数，若否就返回空值。

f. 若m1 和m2 都不存在，则 T 无主元素，返回空值。

  1 #include <stdio.h>
  2 
  3 #include <stdlib.h>
  4 
  5 #include <malloc.h>
  6 
  7 #include <windows.h>
  8 
  9  
 10 
 11 typedef struct snode{
 12 
 13         int data;
 14 
 15         int count;
 16 
 17 }*node;
 18 
 19  
 20 
 21 int checkNum(int *num, int p, int q, int data)
 22 
 23 {
 24 
 25         int count = 0;
 26 
 27         int i;
 28 
 29         for (i = p-1; i < q; i++) {
 30 
 31                 if (num[i] == data) {
 32 
 33                         count++;
 34 
 35                 }
 36 
 37         }
 38 
 39         return count;
 40 
 41 }
 42 
 43  
 44 
 45 node checkAnotherPart(int *num, int len, int p, int q, node nodec)
 46 
 47 {
 48 
 49         nodec->count = checkNum(num, p, q, nodec->data) + nodec->count;  //统计左右两部分元素出现个数
 50 
 51         if (nodec->count > len/2) {   //如若大于n/2,则符合要求返回，否则返回空
 52 
 53                 return nodec;
 54 
 55         }
 56 
 57         else {
 58 
 59                 return NULL;
 60 
 61         }
 62 
 63 }
 64 
 65  
 66 
 67 node checkMaster(int *num, int p, int q)
 68 
 69 {
 70 
 71         node nodetmp = (node)malloc(sizeof(node));
 72 
 73         node nodea = (node)malloc(sizeof(node)); 
 74 
 75         node nodeb = (node)malloc(sizeof(node));
 76 
 77 //递归结束条件
 78 
 79         if (p == q) {
 80 
 81                 nodetmp->data = num[p-1];
 82 
 83                 nodetmp->count = 1;
 84 
 85                 return nodetmp;
 86 
 87         }
 88 
 89         int len = q - p + 1;        //待检查数组长度(未必是从头开始:-p)
 90 
 91         int mid = p + len / 2;      //找数组中间位置(未必是从头开始:+p)
 92 
 93         nodea = checkMaster(num, p, mid-1);  //左半部分递归求解主元素
 94 
 95         nodeb = checkMaster(num, mid, q);    //右半部分递归求解主元素
 96 
 97         if (nodea == NULL && nodeb == NULL) { //两部分都不存在主元素，则返回空
 98 
 99                 return NULL;
100 
101         }
102 
103         if (nodea == NULL && nodeb != NULL) { //左半部分存在，右半部分不存在时，检查左半部分主元素是否合格
104 
105                 return checkAnotherPart(num, len, p, mid-1, nodeb);
106 
107         }
108 
109         if (nodea != NULL && nodeb == NULL) { //左半部分不存在，右半部分存在时，检查右半部分主元素是否合格
110 
111                 return checkAnotherPart(num, len, mid, q, nodea);
112 
113         }
114 
115         if (nodea != NULL && nodeb != NULL) { //左右两部分都存在主元素
116 
117                 if (nodea->data == nodeb->data) { //左右两部分的主元素相同，直接返回
118 
119                         nodea->count = nodea->count + nodeb->count;
120 
121                         return nodea;
122 
123                 }
124 
125                 else { //左右两部分的主元素不同，分别检查其是否为原数组的主元素
126 
127                         node nodec = checkAnotherPart(num, len, p, mid-1, nodeb); 
128 
129                         if (nodec != NULL) {
130 
131                                 return nodec;
132 
133                         }
134 
135                         else {
136 
137                                 return checkAnotherPart(num, len, mid, q, nodea);
138 
139                         }
140 
141                 }
142 
143         }
144 
145 }
146 
147  
148 
149 int main()
150 
151 {
152 
153 int i,n,num[50];
154 
155 printf("please input the number of num[]:");
156 
157 scanf("%d",&n);
158 
159 printf("please input num[]:
");
160 
161 for(i=0;i<n;i++)
162 
163 scanf("%d",&num[i]);
164 
165         node masterNode = checkMaster(num, 1, n);
166 
167 if(masterNode == NULL)
168 
169 printf("the main elemer not exist! 
");
170 
171 else
172 
173 printf("num = %d count = %d
", masterNode->data, masterNode->count);
174 
175 Sleep(10000000);
176 
177 }

代码实现

方法三：主元素个数 > n/2 ，所以主元素的个数减去其它元素的个数仍然大于0。

思路：假定a[0]为主元素mainE，主元素与其它元素的差值为dif，初值为1；然后进行比较，如果下一个元素与mainE相同，则++dif，否则--dif，若为0，则令后继元素为mainE，且dif置1。

分析：时间复杂度为：O(n) 线性

  1 #include <stdio.h>
  2 
  3 #include <stdlib.h>
  4 
  5 #include <windows.h>
  6 
  7  
  8 
  9 int mainElement(int a[], int n)
 10 
 11 {
 12 
 13 int mainE = a[0];
 14 
 15 int dif = 1;
 16 
 17 int i =1;
 18 
 19 int count;
 20 
 21 while(i < n)
 22 
 23 {
 24 
 25 if(a[i] == mainE)
 26 
 27 {
 28 
 29 ++dif;
 30 
 31 }
 32 
 33 else
 34 
 35 {
 36 
 37 --dif;
 38 
 39 if(!dif)
 40 
 41 {
 42 
 43 mainE = a[i+1];
 44 
 45 ++i;
 46 
 47 dif = 1;
 48 
 49 }
 50 
 51 }
 52 
 53 ++i;
 54 
 55 }
 56 
 57  
 58 
 59 //统计mainE的个数，判断mainE是否是主元素
 60 
 61 count = 0;
 62 
 63 for (i = 0; i < n; i++) {
 64 
 65 if (a[i] == mainE) {
 66 
 67 count++;
 68 
 69 }
 70 
 71 }
 72 
 73 if (count > n/2) {
 74 
 75 return mainE;
 76 
 77 }
 78 
 79 return 0;
 80 
 81 }
 82 
 83  
 84 
 85 void main()
 86 
 87 {
 88 
 89 int a[10];
 90 
 91 int i,n,mainE;
 92 
 93 printf("please input the number of a[]:");
 94 
 95 scanf("%d",&n);
 96 
 97 printf("please input a[]:
");
 98 
 99 for(i=0;i<n;i++)
100 
101 scanf("%d",&a[i]);
102 
103 mainE=mainElement(a,n);
104 
105 if (mainE != 0) 
106 
107         printf("main element is %d
", mainE);
108 
109     else 
110 
111         printf("main element not exits
");
112 
113 Sleep(100000);
114 
115 }
116 
117

代码实现