一道面试题，我的第三种解决方案：
int FindNextJumper(int * Array, int * ArraySize, int *CurrentPos, int JumpInterval);
int _tmain(int argc, _TCHAR* argv[])
{
//init data
int ArraySize = 500;
int JumpInterval = 100;
int JumpBeginIndex = 50;
int * array = new int[ArraySize];
for(int i=0;i<ArraySize;++i)
array[i] = i;
//process
int CurrentArraySize = ArraySize;
int CurrentPos = JumpBeginIndex;
while(FindNextJumper(array, &CurrentArraySize, &CurrentPos, JumpInterval));
//disp all jump out sequence
for(int i = ArraySize-1; i>=0; --i)
printf("%d\t", array[i]);
delete []array;
return 0;
}
int FindNextJumper(int * Array, int *ArraySize, int *CurrentPos, int JumpInterval)
{
int nextPos = ((*CurrentPos) + JumpInterval ) % (*ArraySize);
int temp = *(Array + nextPos);
*(Array + nextPos) = *(Array + (*ArraySize) - 1);
*(Array + (*ArraySize) - 1) = temp;
*ArraySize -= 1;
*CurrentPos = nextPos;
return *ArraySize - 1;
}
运行结果：
150 250 350 450 54 154 254 354 454 63
163 263 363 463 77 177 277 377 477 96
196 296 396 19 119 219 319 419 47 147
247 347 447 80 180 280 380 17 117 217
317 417 59 159 259 359 5 105 205 305
405 56 156 256 356 11 111 211 311 411
71 171 271 371 35 135 235 335 3 103
203 303 403 76 176 276 376 53 153 253
353 34 134 234 334 476 475 474 473 8
108 208 308 1 101 201 301 401 99 199
299 0 100 200 300 453 452 451 496 14
114 214 314 27 127 227 327 44 144 244
344 65 165 265 365 90 190 290 18 118
218 318 50 499 498 497 86 186 286 25
125 225 325 68 168 268 390 389 388 387
64 164 264 462 461 460 459 74 174 274
418 458 416 415 98 198 298 378 482 423
435 434 433 410 409 408 407 85 185 285
332 331 330 48 148 248 339 338 337 23
123 223 15 115 215 10 110 210 326 357
324 9 109 209 13 113 213 20 120 220
30 130 230 43 143 243 457 456 455 78
178 278 397 481 24 124 224 51 151 251
81 181 295 294 293 316 315 364 487 362
26 126 226 69 169 472 352 351 62 162
12 112 212 440 368 292 291 372 464 279
38 138 398 483 424 246 245 32 132 406
449 404 73 173 471 470 310 309 287 229
228 82 182 441 233 367 366 37 137 281
258 346 345 304 428 394 393 2 102 221
242 202 412 204 429 206 392 399 207 302
478 469 442 252 343 216 391 369 237 236
486 284 42 142 66 166 92 414 413 468
488 79 444 443 45 145 269 436 370 57
157 432 40 140 84 29 129 426 275 340
342 360 491 241 232 231 88 183 431 430
490 437 321 87 272 16 116 83 328 179
240 91 139 36 194 193 261 385 41 288
492 465 379 184 49 313 421 7 107 480
222 485 446 270 448 131 358 382 484 121
161 400 197 467 104 195 106 341 395 297
6 192 494 158 94 439 141 266 239 160
128 172 402 349 249 188 122 320 425 381
33 152 28 61 136 445 189 273 170 373
89 187 31 72 479 260 374 384 348 289
495 95 52 422 4 493 60 282 97 175
75 420 191 333 383 466 133 306 336 58
146 70 257 167 262 255 361 386 46 155
149 21 329 312 22 355 489 323 67 307
93 55 322 39 238 427 375 267 438 283