某厂java算法题实现及改进【有n个人成一圈,顺序排号(编号为1到n),从第一个人开始报数1到3报数】

时间:2021-05-04 16:06:13

一、第一种实现:

实现比较简单,直接贴现成的代码了,第一种实现:

/**
* 总人数
*
* @param d
*/
private static void sortQuerry1(int d) {
// TODO 先构造一个数组
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 1; i <= d; i++) {
arr.add(i);
}
int xiabiao = -1;
int count = 0;
// 循环查找
int mun = 10;
while (arr.size() > 1) {
xiabiao++;
count++;
if (count == 3) {
System.out.println("移除的是" + arr.get(xiabiao));
arr.remove(xiabiao);
count = 0;
xiabiao = xiabiao - 1;
}
if (xiabiao == (arr.size() - 1)) {
xiabiao = -1;
}
if (arr.size() == 1) {
System.out.println("最后一个剩余的人是:" + arr.get(0));
break;
} } }

二、优化和改进

思考1分钟,上述这种实现的缺点是什么?

时间到了,答案就在Arraylist上面,Arraylist.remove()方法的实现原理是将数组第i个元素之后的所有元素,向前挪一位,这样会导致时间复杂度增加。

如何改进呢?尽量避免ArrayList.remove()方法的使用。下面是一种实现:

private static void sortQuerry2(int d) {
// TODO 先构造一个数组
ArrayList<Boolean> arr = new ArrayList<>(); for (int i = 1; i <= d; i++) {
arr.add(true);
}
int xiabiao = -1;
int count = 0;
int x=0;
// 循环查找
while (true) { xiabiao++;
if(xiabiao>=arr.size()-1)
xiabiao=xiabiao%arr.size();
if(arr.get(xiabiao)==false)
continue;
if (x>=arr.size()-1) {
System.out.println("最后一个剩余的人是:" + (xiabiao+1));
break;
}
count++;
if (count == 3) {
System.out.println("移除的是" + (xiabiao+1));
arr.set(xiabiao, false);
count = 0;
x++;
System.out.println("X是" + x); }
if (xiabiao == (arr.size() - 1)) {
xiabiao = -1;
} }
}

三、测试对比:

两组数据分别是200000,400000

public static void main(String[] args) {
System.out.println("请输入一个数字:");//200000,400000
Scanner scanner = new Scanner(System.in);
int d = scanner.nextInt();
long startTime=System.currentTimeMillis();
sortQuerry1(d);
long endTime=System.currentTimeMillis();
System.out.println("消耗时间:"+(endTime-startTime)/1000.000); }

第一组测试数据200000:

sortQuerry1耗时: 3.919     sortQuerry2耗时:3.304

第二组测试数据400000:

sortQuerry1耗时: 13.443     sortQuerry2耗时:7.157

当数据量大的时候,算法二明显要快于算法1。

以上欢迎交流。