删除csdn网站 约瑟夫环：每隔两个循环删除数组元素--fr csdn

导读就爱阅读网友为您分享以下“约瑟夫环每隔两个循环删除数组元素--frcsdn”资讯希望对您有所帮助感谢您对92to.com的支持!

C/C++面试之算法系列约瑟夫环每隔两个循环删除数组元素求最后删除者的下标问题

×××××××××××××××××××××××××××××××××

有一个数组a[1000]存放0--1000;要求每隔二个数删掉一个数到末尾时循环至开头继续进行求最后一个被删掉的数的原始下标位置原来的数可能是无序的另外数是否重复从题意无法确定。

以8个数为例

{0,1,2,3,4,5,6,7} 0-->1-->2  删 除 -->3-->4-->5(删除)-->6-->7-->0 删除

1

如此循环直到最后一个数被删除。

考点

本题的关键是如何理解删除的概念一种是将其彻底删除将后面未删除的全部前移这将浪费大量的时间用来移动后续数据另外一种只是仍然存在但已经失去意义遍历过程中不管之。

另外一个关键是如何在移动的过程中保持数据的原始下标因为数据本身可能是无序的下标和数据可能没有关系并且还可能重复

性能分析

时间效率循环队列法由于每次扫描的数都是未删除的时间整体效率最高标志数组法只是将此数标记为删除了但遍历时仍然要扫描链表法要建立链时间效率低

空间效率标志数组法未申请额外的空间空间效率最高循环队列法至少申请第一次未删除的空间另外作为接口函数来实现的话 由于新申请的空间不能与传入的数组地址相连 因此有局限性链表法额外建立链表空间效率最低

约束因素

2

对于只读数组普通的标志法都不能用了将高位置1遍历完后清除的方法借鉴意义最高 时间和空间效率最均衡链表法可以处理只读数组的问题循环队列法此时无法实现当然对于标志法可以额外申请空间保存标志也可以处理只读问题但空间效率下来了

面试中的最优选择

将高位置1遍历完后清除效率最高

数组方式二的优化版本三层while程序的逻辑功能划分明确

数组方式一的优化版本程序的结构易懂清晰

循环队列法最难想到个人认为相对于标志数组更有创新性

××××××××××××××××××××××××××××××××

方法1访问原数组置删除标志

这题目如果是面试题那考的就是用数组增加难度的。

××××××××××××××××××××××××××××××××

数组方式一const int size=1000;void ArrayTest1 (void)

{

3

int arr[size];int currentSize=size; //指示当前数组中还剩余有效元素的个数 为1时表示删除/完毕int count=0; //计数用for(int k=0;k<size;k++)

{arr[k]=k;

}

// i用循环计数终止条件是删除的只剩最后一个数了for(int i=0;(i<size) && (currentSize!=1);i=(i+1)%size)

{if(a rr[i]!=-1) //1为已经删除的标志未删除对之计数 已经删除的则看下一个

{

//按照计数间隔计数达到间隔时删除数据if(c o unt>=0 && c o unt<2)

{count++;

}else if( count==2) //逻辑有点乱

4

{arr[i]=-1;//将此元素做上标记表示删除此时的元素curre ntSize--;//有效元素减一count=0;//并将计数值归零

}

}

}for(int j=0;j<size;j++) //浪费时间啊

{if(a rr[j]!=-1)

{cout<<”the result is :”<<j<<endl;break;

}

}

}

优化版本宏定义意义明确更改方便是良好的编程习惯要在笔试面试中展现这种特点

删除数据时保存了其位置和实际的数据值无需最后一次扫描

三层判断条件功能清晰 总数是否删除是否达到间隔

5

值

#define SIZE 1000

#define STEP 2

#define DELFLAG(SIZE+1)void ArrayTest1Opt(void)

{int arr[SIZE];int currentSize=SIZE; //指示当前数组中还剩余有效元素的个数为0时表示删除/完毕int count=0; //计数用int i=0;int lastdelindex= 0; //用来保存每次删除值的位置不用留最后一个然后遍历int lastdelvalue = 0; //用来保存每次删除值不用留最后一个然后遍历for(int k=0;k<SIZE;k++)

{arr[k]=k;

}

// i用循环计数终止条件是删除所有的数了

6

//for(int i=0;currentSize!=0; i=(i+1)%SIZE)while(curre ntSize!=0)

{if(arr[i]!=DELFLAG) //DELFLAG为已经删除的标志未删除对之计数 已经/删除的则看下一个

{

//按照计数间隔计数达到间隔时删除数据if(c o u nt++==S TE P) //注意的位置

{lastdelindex=i; //用来保存每次删除值的位置lastdelvalue = arr[i] ; //用来保存每次删除值的位置arr[i]=DELFLAG;//将此元素做上标记表示删除此时的元素curre ntSize--;//有效元素减一count=0;//并将计数值归零

}

}i=(i+1)%SIZE;

}cout<<”the original array location of the last del

7

value is:“<<lastdel<<e ndl;

}

××××××××××××××××××××××××××××××××

数组方式二两重w h i le循环将间隔计数的直接

写成了程序未用循环这样移植性差了

//#define SIZE 1000

//#define STEP 2

//#define DELFLAG(SIZE+1)void ArrayTest2(void)

{int a rr[S IZE];for(int i=0;i<SIZE;++i)arr[i]=i; //实际情况并非一定如此啊int j=0;int count=0;while(count<S IZE-1) // 999保留了最后一个未删除的数

{

8

while(arr[j%1000]==DELFLAG)j=(++j)%SIZE;j=(++j)%SIZE; //第一个未访问的数while(arr[j%SIZE]==DELFLAG)j=(++j)%SIZE;j=(++j)%SIZE; //第二个未访问的数while(arr[j%SIZE]==DELFLAG)j=(++j)%SIZE;arr[j]=DELFLAG; //删除第三个未访问的数++c o u nt;

}while(arr[j]==DELFLAG) //扫描最后一个未删除的数j=(++j)%SIZE;cout<<j<<endl;

}

9