一道面试题

robin254817

最近做的一道面试题：一个整形数组 int a【1000】，内赋值0-999.然后从头开始每隔2个值删除一个，循环下去。例如：a[7],0-1-2(删除)-3-4-5（删除）-6-0-1（删除）...如此循环下去，直到全部删除完毕。
求最后一个删除值在数组a中的下标。

最近头脑不灵光，真没好思路。大家给点拨点拨，多谢了。

tempname2

约瑟夫环？

xinglp

经常被面也经常面人这个题,可是这个东西用在哪里呢?

fiema

约瑟夫环的简化版……

雨夜流星

603 ？

witer666

好像是607

Magic_LP

这个我也遇到过，因为本人比较笨，数学基础不是很好，所以也没有什么特别取巧的办法，就是简单的循环删除。我记得当时我是用单向循环链表来做的，从头节点开始循环遍历，然后删除，直到一个节点的next是它本身，则说明只是最后剩下的，即为所求。

lwrsmy

循环999次 做标记
未标记的就是最后一个

cobras

我算出来郎个是976呢

1. 
   
2. #include <stdio.h>
   
3. #include <string.h>
   
4. 
   
5. #define LEN(a) (sizeof(a)/sizeof(a[0]))
   
6. 
   
7. #define COUNT     1000
   
8. 
   
9. int get_valid(const int *data, int len, int from, int *o_pos)
   
10. {
    
11.         int i;
    
12.         for (i = from; i < len; i++) {
    
13.                 if (data[i] == 0) {
    
14.                         *o_pos = i;
    
15.                         return 0;
    
16.                 }
    
17.         }
    
18.         for (i = 0; i < from; i++) {
    
19.                 if (data[i] == 0) {
    
20.                         *o_pos = i;
    
21.                         return 0;
    
22.                 }
    
23.         }
    
24.         return -1;
    
25. }
    
26. 
    
27. int main(void)
    
28. {
    
29.         int data[COUNT];
    
30.         int i;
    
31. 
    
32.         memset(data, 0, sizeof(data));
    
33.         i = 0;
    
34.         while (get_valid(data, LEN(data), i, &i) == 0) {
    
35.                 get_valid(data, LEN(data), i + 1, &i);
    
36.                 data[i] = 1; /* delete */
    
37.                 continue;
    
38.         }
    
39.         printf("last exist: %d\n", i);
    
40.         return 0;
    
41. }
    

复制代码

amarant

感觉这样肯定走了弯路