Java 程序使用列表查找 0 到 n 中的 'Lucky' 个数字

Question

我必须编写一个程序来找到从 0 到任意数字 n 的所有幸运数字。
这是一个幸运数字:

考虑自然数序列。
1、2、3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20、21、22、23、24、25…… ……………………………….
删除每隔一个数字产生序列
1、3、5、7、9、11、13、15、17、19、21、23………………………….
删除每三个数字产生序列
1、3、7、9、13、15、19、21、25………………………….

这个过程通过删除第四个、第五个……等等无限期地继续下去，直到经过固定数量的步骤后，某些自然数无限期地保留下来。这些被称为幸运数字。

我决定为此尝试使用 ArrayList。但我似乎无法弄清楚这一点。我已经尝试了好几天了。
这是代码:

import java.util.*;
class luckyy
{
public static void main(String args[])
{

    Scanner scan = new Scanner(System.in);
    System.out.println("Enter n: ");

    int i, n, index;
    n = scan.nextInt();     
    ArrayList <Integer> ele = new ArrayList <Integer> (n);
    //storing in a list
    for(i = 1;i<=n;i++)
    {
        ele.add(i);
    }
    System.out.println(ele);
    int count = 2;
    index = 1;
    System.out.println("Size: "+ele.size());
    while(count<ele.size())
    {
        for(i = 0;i<ele.size();i++)
        {
            int chk = ele.get(i);
            if(chk%count == 0)
            {
                ele.remove(i);
            }                
        }
        count++;           
    }
    System.out.print(ele);        
}
}

这给出了输出:
[1, 5, 7]
当期望的输出是:
[1, 3, 7]

所以，如果这段代码糟糕到令人反感，那我很抱歉哈哈...但我真的很感激任何帮助。我刚开始成为一名程序员，还有很多东西要学，希望得到任何建议。感谢任何试图帮助我的人!

Answer 1

首先，在我看来，您对预期输出的假设是不正确的。根据你描述的任务，输出应该是这样的:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25] // every 2nd number removed
[1, 3, 7, 9, 13, 15, 19, 21, 25] // every 3rd number removed
[1, 3, 7, 13, 15, 19, 25] // every 4th number removed
[1, 3, 7, 13, 19, 25] // every 5th number removed
[1, 3, 7, 13, 19] // 6th number removed = final output

除此之外，我还看到了两个错误。

1. 您想删除“每第 n 个数字”，因此您不想测试这些值，而是要测试它们在列表中的位置/索引。
2. 每当您从 ArrayList 中删除一个元素时，后续元素的索引和列表的大小都会减少 1。意味着如果您从删除“2”开始，下一个要删除的数字将是“5” "，而不是所需的 "4"(假设您正在测试索引，而不是值)。一种解决方案是测试从列表末尾开始的索引。在这种情况下，删除元素后较高的索引发生变化并不重要，因为您已经传递了它们。

编辑

根据@Kedar Mhaswade 的要求编辑了答案，以提供一些代码以测试如何从列表末尾删除元素。

这是我的第一种方法:

  List<Integer> removeBackward(List<Integer> numbers) {
    int count, sPos;
    count = 2;
    while(count<=numbers.size())
    {
      for(sPos = numbers.size(); sPos >= numbers.size()-count; sPos--)
      {
        if(0 == sPos%count) {
          break;
        }
      }
      for(int pos = sPos; pos > 0; pos=pos-count)
      {
        numbers.remove(pos-1);
      }
      count++;           
    } 
    return numbers;
  }

我做了一些测试(见下文)，结果它对小的数字集(< 12000)表现相当好。在较大的集合上，@Kedar Mhaswade 的第二种方法(为要保留的元素维护一个额外的列表)优于这种方法。

因此我尝试了第二种方法:

想法是，当第一步将删除一半元素并且要保留的元素数量逐步减少时，无需为保留元素维护第二个列表。所以我简单地将要保留的元素移动到同一个列表的末尾并维护额外的指针，以便知道保留元素的范围。在这个过程结束时，只需要从列表的末尾提取最终结果。

List<Integer> retainedAtEnd(List<Integer> numbers) {
  int removeX, baseQty, retainedQty, basePos, retainedPos;
  removeX = 1;
  baseQty = numbers.size();
  while(removeX <= baseQty)
  {
    removeX++;
    basePos = numbers.size();
    retainedPos = basePos;
    retainedQty = 0;
    for(int checkPos = baseQty; checkPos >= 1; checkPos--)
    {
      if(0 != checkPos%removeX) 
      {
        basePos = numbers.size()-baseQty+checkPos;
        numbers.set(retainedPos-1, numbers.get(basePos-1));
        retainedPos--;
        retainedQty++;
      }
    }
    baseQty = retainedQty;
  }
  return numbers.subList(numbers.size()-baseQty, numbers.size());
  // return new ArrayList(numbers.subList(numbers.size()-baseQty, numbers.size()));
}

不幸的是，根据我的测试，这种方法在小集合 (<12000) 上表现不佳。它无法与第一种或@Kedar Mhaswade 的第二种方法竞争，但在更大的集合上，它优于两者。

这是我测试的方式:

    public void test() {
      int n = 1000;     
      long start;
      System.out.println("Testing with " + n + " numbers ..."); 

      System.out.println("Test removing elements backwards:");
      List<Integer> numbers1 = Stream.iterate(1, k -> k + 1).limit(n).collect(Collectors.toList());
      start = System.nanoTime();    
      List<Integer> out1 = this.removeBackward(numbers1);
      System.out.println("Time taken:" + (System.nanoTime() - start));
  //    System.out.println(out1);

      System.out.println("Test maintaining extra list for retained elements:");
      List<Integer> numbers2 = Stream.iterate(1, k -> k + 1).limit(n).collect(Collectors.toList());
      start = System.nanoTime();    
      List<Integer> out2 = this.extraRetainedList(numbers2);
      System.out.println("Time taken:" + (System.nanoTime() - start));
  //    System.out.println(out2);

      System.out.println("Test collecting retained elements at end of list:");
      List<Integer> numbers3 = Stream.iterate(1, k -> k + 1).limit(n).collect(Collectors.toList());
      start = System.nanoTime();    
      List<Integer> out3 = this.retainedAtEnd(numbers3);
      System.out.println("Time taken:" + (System.nanoTime() - start));
  //    System.out.println(out3);

      System.out.println("Test maintaining extra list for elements to remove:");
      List<Integer> numbers4 = Stream.iterate(1, k -> k + 1).limit(n).collect(Collectors.toList());
      start = System.nanoTime();    
      List<Integer> out4 = this.extraDeletedList(numbers4);
      System.out.println("Time taken:" + (System.nanoTime() - start));
  //    System.out.println(out4);
    }