Java中最适合的数据结构是什么？如何有效地实现它？

Question

这是针对代码战的编码挑战。挑战的条件：考虑一个序列u，其中u定义如下：

The number u(0) = 1 is the first one in u.

For each x in u, then y = 2 * x + 1 and z = 3 * x + 1 must be in u too.

There are no other numbers in u.

Ex: u = [1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27, ...]

1 gives 3 and 4, then 3 gives 7 and 10, 4 gives 9 and 13, then 7 gives 15 and 22 and so on...

Task:

Given parameter n the function dbl_linear (or dblLinear...) returns the element u(n) of the ordered (with <) sequence u (so, there are no duplicates).

我的天真实现只生成250000个数字：

import java.util.List;

import java.util.ArrayList;

import java.util.TreeSet;

import java.util.Set;

import java.util.HashSet;

class DoubleLinear {

        private static Set<Integer> nums;

        private static Set<Integer> seen;

        public static int dblLinear (int n) {

                nums = new TreeSet<>();

                seen = new HashSet<>();

                nums.add(1);

                for (int i = 0; i < 17; i++) {

                        generateNumbers();

                }

                List<Integer> numList = new ArrayList(nums);

                return numList.get(n);

        }

        public static void generateNumbers () {

                for (int x : new TreeSet<Integer>(nums)) {

                        if (seen.contains(x)) continue;

                        if (nums.size() >= 250000) break; 

                        int y = (2*x) + 1, z = (3*x) + 1;

                        if (y > 0) nums.add(y);

                        if (z > 0) nums.add(z);

                        seen.add(x);

                }

        }

}

我很好奇我可以用什么其他结构来提高效率，因为我显然缺少解决这个问题所需的知识。

Answer 1

您可以将数字存储在HashMap中以存储数字。使用x作为键，使用（Y或Z）作为值。