剑指offer之圆圈最后剩下的数

1 问题

求圆圈最后剩下的数，比如数组0, 1, 2 ,3 ,4围城一个环，我们每次去掉第三个数字，删除的前4个数字依次是2, 0, 4, 1，最后剩下的数字是3

                      0
     
             4               1
     
               3           2


2 思路

我们用list,我们要支持环就这样,如果发现当前指针指向是尾巴的时候，我们把它指向链表的开始。

 
 
3 代码实现

    #include <iostream>
    #include <list>
     
    using namespace std;
     
    int getIndex(int n, int m)
    {
        if (n < 1 || m < 1)
        {
            return -1;
        }
        list<int> numbers;
        for (int i = 0; i < n; ++i)
        {
            numbers.push_back(i);
        }
        list<int>::iterator current = numbers.begin();
        while(numbers.size() > 1)
            {
            for(int i = 1; i < m; ++i)
            {
                current++;
                //指针向右移动的时候需要判断是否到了数组尾巴
                if (current == numbers.end())
                {
                    current = numbers.begin();
                }
            }
            //指针向右移动的时候需要判断是否到了数组尾巴
            list<int>::iterator next = ++current;
            if (next == numbers.end())
            {
                next = numbers.begin();
            }
            current--;
                    //删除指定的元素
            numbers.erase(current);
            current = next;
        }
        return *(current);
    }
     
    int main()
    {
        int a[] = {0, 1, 2, 3, 4};
        int index = getIndex(5, 3);
        if (-1 != index)
            {
            std::cout << a[index] << std::endl;
        }
        return 0;
    }

 
4 运行结果

3


 
5 总结

如果我们需要环的数据结构，我么可以使用list数据结构，然后当指针指向尾巴的时候我们指向头。

    list<int> numbers;
    for (int i = 0; i < n; ++i)
    {
        numbers.push_back(i);
    }
    list<int>::iterator current = numbers.begin();
    for (int i = 1; i < m; ++i)
    {
        ++current;
        if (current == numbers.end())
        {
            current = numbers.begin();
        }
    }   

 


 

作者：chen.yu
深信服三年半工作经验，目前就职游戏厂商，希望能和大家交流和学习,
微信公众号：编程入门到秃头 或扫描下面二维码
零基础入门进阶人工智能(链接)