原帖由 decisiontree 于 21-5-2009 18:17 发表
呵呵，恕我愚笨。我知道总长度为n。请明确解释下三个数组的问题。特别是排在中间那个数组的指针走向，向左走还是向右走。然后看看这个办法能不能用到一百一千个数组里。
相信没有什么东西比一段代码更有说服力了。我用C语言实现了上面说的那个算法。- 1 #include <stdio.h>
- 2 #include <stdlib.h>
- 3 #include <unistd.h>
- 4 #include <sys/types.h>
- 5 #include <time.h>
- 6 #include <values.h>
- 7 #include <string.h>
- 8
- 9
- 10 /*
- 11 * randomly choose the len of array A , B and C from 1024 to 2048
- 12 * and randomly choose the value of <i>th from 100 to 500
- 13 *
- 14 * note that the start index of C array is 0 and the start number of ith is 1
- 15 *
- 16 */
- 17
- 18 void generate(int x[], size_t len)
- 19 {
- 20 int k;
- 21
- 22 for(k=0; k<len; k++)
- 23 {
- 24 x[k] = rand() % 9999;
- 25 }
- 26 }
- 27
- 28 int value_compare(const void * v1, const void * v2)
- 29 {
- 30 const int * vv1 = (const int *)v1;
- 31 const int * vv2 = (const int *)v2;
- 32
- 33 return (* vv1) - (* vv2);
- 34 }
- 35
- 36 int main(int argc, char ** argv)
- 37 {
- 38 int len[3], tlen;
- 39 int * seq[3];
- 40 int base[3];
- 41 int ith;
- 42 int count, lowest_pace;
- 43 int k;
- 44 int curpace, diff;
- 45
- 46 srand(time(NULL));
- 47
- 48 tlen = 0;
- 49 for(k=0; k<3; k++)
- 50 {
- 51 len[k] = rand() % 1024 + 1024;
- 52 seq[k] = (int *)malloc(len[k] * sizeof(int));
- 53 generate(seq[k], len[k]);
- 54 qsort(seq[k], len[k], sizeof(int), value_compare);
- 55 tlen += len[k];
- 56 }
- 57
- 58 ith = rand() % 400 + 100;
- 59
- 60 //debug
- 61 printf("N = %d, A = %d, B = %d, C = %d, ith = %d\n", tlen, len[0], len[1], len[2], ith);
- 62
- 63 count = 0;
- 64 lowest_pace = ith / 3;
- 65 base[0] = base[1] = base[2] = 0;
- 66
- 67 int min, minSeq;
- 68
- 69 while(lowest_pace > 1)
- 70 {
- 71 printf("DEBUG lowest_pace = %d, A_base = %d, B_base = %d, C_base = %d\n",
- 72 lowest_pace, base[0], base[1], base[2]);
- 73
- 74 diff = ith - (base[0] + base[1] + base[2] + 3 * lowest_pace);
- 75 int pace[3];
- 76 int k;
- 77
- 78 minSeq = -1;
- 79
- 80 pace[0] = pace[1] = pace[2] = lowest_pace;
- 81
- 82 for(k=0;diff>0; --diff, k++)
- 83 {
- 84 pace[k]++;
- 85 }
- 86
- 87 int total_pace[3];
- 88
- 89 for(k=0; k<3; k++)
- 90 {
- 91 total_pace[k] = base[k] + pace[k];
- 92 }
- 93
- 94
- 95 min = MAXINT;
- 96
- 97 for(k=0; k<3; k++)
- 98 {
- 99 if(seq[k][total_pace[k]] < min)
- 100 {
- 101 min = seq[k][total_pace[k]];
- 102 minSeq = k;
- 103 }
- 104 }
- 105
- 106 base[minSeq] += pace[minSeq];
- 107
- 108 curpace = 0;
- 109 for(k=0; k<3; k++)
- 110 {
- 111 curpace += base[k];
- 112 }
- 113
- 114 lowest_pace = (ith - curpace) / 3;
- 115 }
- 116
- 117 curpace = base[0] + base[1] + base[2];
- 118 diff = ith - curpace;
- 119
- 120
- 121 k = 0;
- 122
- 123 while(diff > 0)
- 124 {
- 125 min = MAXINT;
- 126 minSeq = -1;
- 127
- 128 for(k=0; k<3; k++)
- 129 {
- 130 if(min > seq[k][base[k]])
- 131 {
- 132 min = seq[k][base[k]];
- 133 //base[k] ++;
- 134 minSeq = k;
- 135 }
- 136 }
- 137
- 138 base[minSeq] ++;
- 139 diff --;
- 140
- 141 }
- 142
- 143 printf("\n");
- 144 printf("<%d>th number is %d, seq is %d, base[0] = %d, base[1] = %d, base[2] = %d\n",
- 145 ith, seq[minSeq][base[minSeq]-1], minSeq, base[0], base[1], base[2]);
- 146
- 147 int * nseq = (int *)malloc(sizeof(int) * tlen);
- 148 memcpy(nseq, seq[0], sizeof(int) * len[0]);
- 149 memcpy((char *)nseq + len[0] * sizeof(int), seq[1], sizeof(int) * len[1]);
- 150 memcpy((char *)nseq + len[0] * sizeof(int) + len[1] * sizeof(int), seq[2], sizeof(int) * len[2]);
- 151
- 152 qsort(nseq, tlen, sizeof(int), value_compare);
- 153
- 154 printf("<%d>th should be %d\n", ith, nseq[ith-1]);
- 155
- 156 return 0;
- 157 }
- N = 4242, A = 1102, B = 1892, C = 1248, ith = 144
- DEBUG lowest_pace = 48, A_base = 0, B_base = 0, C_base = 0
- DEBUG lowest_pace = 32, A_base = 0, B_base = 48, C_base = 0
- DEBUG lowest_pace = 21, A_base = 0, B_base = 48, C_base = 32
- DEBUG lowest_pace = 14, A_base = 22, B_base = 48, C_base = 32
- DEBUG lowest_pace = 9, A_base = 22, B_base = 62, C_base = 32
- DEBUG lowest_pace = 6, A_base = 22, B_base = 62, C_base = 41
- DEBUG lowest_pace = 4, A_base = 22, B_base = 62, C_base = 47
- DEBUG lowest_pace = 2, A_base = 27, B_base = 62, C_base = 47
- <144>th number is 323, seq is 1, base[0] = 29, base[1] = 68, base[2] = 47
- <144>th should be 323
- N = 5364, A = 1788, B = 2025, C = 1551, ith = 220
- DEBUG lowest_pace = 73, A_base = 0, B_base = 0, C_base = 0
- DEBUG lowest_pace = 49, A_base = 0, B_base = 73, C_base = 0
- DEBUG lowest_pace = 32, A_base = 49, B_base = 73, C_base = 0
- DEBUG lowest_pace = 22, A_base = 49, B_base = 73, C_base = 32
- DEBUG lowest_pace = 14, A_base = 71, B_base = 73, C_base = 32
- DEBUG lowest_pace = 9, A_base = 71, B_base = 88, C_base = 32
- DEBUG lowest_pace = 6, A_base = 71, B_base = 88, C_base = 41
- DEBUG lowest_pace = 4, A_base = 71, B_base = 88, C_base = 47
- DEBUG lowest_pace = 3, A_base = 76, B_base = 88, C_base = 47
- DEBUG lowest_pace = 2, A_base = 76, B_base = 91, C_base = 47
- <220>th number is 418, seq is 2, base[0] = 77, base[1] = 94, base[2] = 49
- <220>th should be 418
- N = 4915, A = 2045, B = 1040, C = 1830, ith = 345
- DEBUG lowest_pace = 115, A_base = 0, B_base = 0, C_base = 0
- DEBUG lowest_pace = 76, A_base = 115, B_base = 0, C_base = 0
- DEBUG lowest_pace = 51, A_base = 115, B_base = 0, C_base = 76
- DEBUG lowest_pace = 34, A_base = 115, B_base = 51, C_base = 76
- DEBUG lowest_pace = 22, A_base = 150, B_base = 51, C_base = 76
- DEBUG lowest_pace = 15, A_base = 150, B_base = 51, C_base = 98
- DEBUG lowest_pace = 10, A_base = 150, B_base = 66, C_base = 98
- DEBUG lowest_pace = 7, A_base = 150, B_base = 66, C_base = 108
- DEBUG lowest_pace = 4, A_base = 157, B_base = 66, C_base = 108
- DEBUG lowest_pace = 3, A_base = 157, B_base = 66, C_base = 112
- DEBUG lowest_pace = 2, A_base = 161, B_base = 66, C_base = 112
- <345>th number is 655, seq is 2, base[0] = 164, base[1] = 67, base[2] = 114
- <345>th should be 655
|
发表于 20-5-2009 20:11:39
收藏
赞
踩
楼主
。可是偏偏去年碰到几个面试/笔试就有，有什么比较容易的办法不？大家帮忙给个意见？