使用列表从0到n查找“Lucky”数字的Java程序

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

首先，在我看来，你对预期产出的假设是不正确的。根据您描述的任务，out应该如下所示：

[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”(假设您正在测试索引，而不是值)。其中一个解决方案是测试从列表末尾开始的索引。在这种情况下，删除元素后更改更高的索引并不重要，因为您已经传递了它们。

编辑

对@的请求进行编辑，以提供一些代码，以测试如何从列表末尾删除元素。

这是我的第一个方法：

  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的第二种方法(为元素保留额外的列表)优于这种方法。

因此，我尝试了第二种方法：

这样做的想法是，在第一步删除一半的元素时，不需要为保留的元素保留第二个列表，而保留的元素数量将逐步减少。因此，我只需将要保留的元素移到相同列表的末尾，并维护其他指针，以了解保留元素的范围。在流程结束时，只需要从列表的末尾提取最终结果。

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);
    }

Answer 2

这是个棘手的问题！我以一种稍微不同的方式进行了研究，并使用另一个列表来存储已删除的元素。这是必需的，因为我选择了数据结构。因为我只想使用整数，而且我使用的是ArrayList，所以每次删除元素时，列表都会立即调整。我们真正需要做的是标记要删除的元素。有不止一种方法可以做到这一点，但我选择了维护另一个已删除元素列表(因为所有元素都是唯一的，使用这个想法是可以的)。

这是我第一次尝试：

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/** <p>
 *      Find the lucky numbers amongst natural numbers from 1 to n.
 *      Here's how you find <a href="http://stackoverflow.com/questions/35673769/java-program-to-find-lucky-numbers-from-0-to-n-using-lists">Lucky numbers</a>.
 * </p>
 * Created by kmhaswade on 2/27/16.
 */
public class Lucky {
    public static void main(String[] args) {
        printLucky1(Integer.valueOf(args[0]));
    }
    private static void printLucky1(int n) {
        List<Integer> numbers = Stream.iterate(1, k -> k + 1).limit(n).collect(Collectors.toList());
        System.out.println(numbers);
        int delIndex = 1; // index of the element to be removed, we start with 2nd element
        while (delIndex < numbers.size()) {
            List<Integer> deleted = new ArrayList<>();
            for (int i = delIndex; i < numbers.size(); i += (delIndex + 1)) {
                deleted.add(numbers.get(i));
            }
            numbers.removeAll(deleted); // expensive operation!
            System.out.println(numbers);
            delIndex += 1;
        }
        System.out.println("number of lucky numbers:" + numbers.size());
        System.out.println(numbers);
    }
}

这行得通！但是对于非常长的列表，这是非常慢的，因为昂贵的操作：numbers.removeAll(deleted) --我们正在从ArrayList中删除一组元素，在每次删除时必须移动所有受影响的元素！

例如，使用第一个100_000自然数，在我的计算机上大约需要10秒。显然，我在寻找另一种选择。如果我们设计另一个列表并收集我们想要保留的元素，那么在下一次迭代中，这个保留元素的列表将成为我们要操作的列表？这看起来会更好，因为没有删除所涉及的元素。您仍然需要另一个ArrayList来收集元素。在分析方面，这是一个O(n)附加空间(或c.n，在其中c ~ 0.5)。

这是我的第二次尝试：

private static void printLucky2(int n) {
    List<Integer> numbers = Stream.iterate(1, k -> k + 1).limit(n).collect(Collectors.toList());
    System.out.println(numbers);
    int delIndex = 1; // index of the element to be removed, we start with 2nd element
    while (delIndex < numbers.size()) {
        List<Integer> retained = new ArrayList<>();
        for (int i = 0; i < numbers.size(); i += 1)
            if ((i+1) % (delIndex + 1) != 0)
                retained.add(numbers.get(i));
        numbers = retained;
        System.out.println(numbers);
        delIndex += 1;
    }
    System.out.println("number of lucky numbers:" + numbers.size());
    System.out.println(numbers);
}

可能会有更多的改进，因为对于非常大的输入，该算法所花费的时间仍然是不可接受的(将对此改进进行工作)。但我已经看到了两个数量级的改进！

这是完整代码。我确保两个方法都返回相同的列表(list1.equals(list2)返回true)，下面是我的计算机上的输出(带有第一个100_000号)：

[1, 3, 7, ...]
number of lucky numbers: 357
time taken: 6297
number of lucky numbers: 357
[1, 3, ...]
time taken: 57

Answer 3

对于那些仍然感兴趣的人，我找到了另一种方法来做到这一点。它并不是革命性的，它使用了很多在这个帖子上的人告诉我的东西，但是它概括了我猜的所有建议。我觉得贴出我的答案是公平的。因此，它涉及迭代每个元素，在每一轮计数中存储需要删除的所有元素，然后使用removeAll函数在计数增加之前删除它们。这是所有感兴趣的人的完整代码。任何意见也将受到欢迎。

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);
    ArrayList <Integer> toRemove = new ArrayList <Integer> (n);
    //storing in a list
    for(i = 1;i<=n;i++)
    {
        ele.add(i);
    }
    System.out.println(ele);
    int count = 2;     
    System.out.println("Size: "+ele.size());
    while(count<=ele.size())
    {

        for(i = 0;i<ele.size();i++)
        {
            if((i+1)%count == 0)
            {                    
                toRemove.add(ele.get(i));
            }                
        }
        ele.removeAll(toRemove);
        toRemove.clear();
        count++;
    }
     System.out.println(ele);
}
}

就是这样！起作用了，孩子，我很高兴！如果任何人有任何进一步的建议，或任何其他我学习或结帐，您完全欢迎评论。再次感谢各位！