题目:给定n个数编号从1~n形成一个环,每次删除环中的第m个数,求最后一个被删除的数。
方案一:把n个数构造成一个环形链表,每次遍历链表删除一个。总的时间复杂度O(n*m),还需要O(n)的空间
方案二:利用数学递推式。详情请见
链表法
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; //链表结点 struct ListNode{ int value; ListNode* nextNode; }; //建立链表 void BuildList(ListNode **headNode, int *arrNum, int n){ if(arrNum == NULL || n <= 0){ return; } (*headNode)->value = arrNum[0]; (*headNode)->nextNode = NULL; ListNode *preNode = (*headNode); //建立剩下的n-1个点 for(int i = 1; i < n; i++){ ListNode *newNode = new ListNode(); newNode->value = arrNum[i]; newNode->nextNode = NULL; preNode->nextNode = newNode; preNode = newNode; } preNode->nextNode = *headNode; } //删除n-1个点 int GetLastNum(ListNode *headNode, int n, int m){ if(headNode == NULL || n <= 0 || m <= 0){ throw exception("error"); } int count = n; ListNode *pNode = headNode; while(count > 1){ int pos = 1; while(pos < m-1){ ++pos; pNode = pNode->nextNode; } ListNode *tmpNode = pNode->nextNode; pNode->nextNode = tmpNode->nextNode; delete tmpNode; tmpNode = NULL; --count; pNode = pNode->nextNode; } return pNode->value; } //遍历链表 void PrintListNode(ListNode *headNode){ ListNode *pNode = headNode; cout<<pNode->value<<endl; pNode = pNode->nextNode; while(pNode != headNode){ cout<<pNode->value<<endl; pNode = pNode->nextNode; } } int main(){ //样例 int arrNum[] = {1,2,3,4,5}; ListNode *headNode = new ListNode(); BuildList(&headNode, arrNum, 5); cout<<GetLastNum(headNode, 5, 3)<<endl; return 0; }