第十八题
题目:n 个数字(0,1,…,n-1)形成一个圆圈,从数字0 开始,
每次从这个圆圈中删除第m 个数字(第一个为当前数字本身,第二个为当前数字的下一个数
字)。
当一个数字删除后,从被删除数字的下一个继续删除第m 个数字。
求出在这个圆圈中剩下的最后一个数字。
分析:
这道题有很多解法,http://blog.csdn.net/v_july_v/article/details/6870251 给出了目前最快的算法。
本题目使用了链表的增删,直到剩余一个节点的时候即为最后输出的值,设表长度为n,每次删除第m个元素,则复杂度为mn。
代码:
#include<iostream> using namespace std; struct node { node * nodeNext; node * nodePrevious; int value; }; int listConDelete(int length, int k) { if(length<1)return -1; if(k<1)return -1; node * nodeHead, * nodeCurrent,* list; nodeCurrent = new struct node(); nodeCurrent->value = 0; nodeCurrent->nodeNext = NULL; nodeCurrent->nodePrevious = NULL; nodeHead = nodeCurrent; list = nodeCurrent; for(int i = 1; i < length; i++) { nodeCurrent = new struct node(); nodeCurrent->value = i; list->nodeNext = nodeCurrent; nodeCurrent->nodePrevious = list; list = nodeCurrent; } nodeCurrent->nodeNext = nodeHead; nodeHead->nodePrevious = nodeCurrent; list = nodeHead; node * tempDele; while(list!=list->nodeNext) { int index = 1; while(index < k) { list = list->nodeNext; index++; } tempDele = list; list->nodePrevious->nodeNext = list->nodeNext; list->nodeNext->nodePrevious = list->nodePrevious; list = list->nodeNext; //cout<<tempDele->value<<" "; delete tempDele; } return list->value; } int main() { cout<<listConDelete(9,1)<<endl; cout<<listConDelete(9,0)<<endl; cout<<listConDelete(9,4)<<endl; return 0; }