2回線形Java

Question

これは私が解決しようとしている問題です。私は正確な解決策を探しているのではなく、誰かが私に解決方法を導くことができる場合のみです。

説明： ここで、uは次のように定義されます。 番号u（0）= 1がuの最初のものです。 uの各xについて、y = 2 * x + 1かつz = 3 * x + 1もuになければなりません。 uには他の番号はありません。 例：u = [1,3,4,7,9,10,13,15,19,21,22,27、...] 1は3と4を​​与え、3は7と10を与え、4は9と13の場合7は15と22など... タスク： パラメータnを指定すると、関数dbl_linear（またはdblLinear ...）は、順序付けられた（<の）シーケンスuの要素u（n）を返します。 例： dbl_linear（10）が22 注意を返す必要があります：

私は上記の問題のために自分のソリューションを持っているが、私は、関数dbl_linearへの入力として、より大きなインデックス番号を持っていたときに解決策が故障し、効率

に注意を集中 。インデックス番号が6000または10,000の場合と同様です。

ここでは、より小さい範囲で機能する独自のソリューションです。

public static int dblLinear (int n) { 
     // your code 
     System.out.println("the input range is " + n); 
     ArrayList<Integer> possibleOutputs = new ArrayList<Integer>(); 
     //LinkedHashSet<Integer> possibleOutputsWithoutDuplicates = new LinkedHashSet<Integer>(); 
     possibleOutputs.add(1); 
     for(int i=0; i<n; i++) 
     { 
      int y = 2*possibleOutputs.get(i) + 1; 
      int z = 3*possibleOutputs.get(i) + 1; 

      if(!possibleOutputs.contains(y)) 
      { 
       possibleOutputs.add(y); 
      } 
      if(!possibleOutputs.contains(z)) 
      { 
       possibleOutputs.add(z); 
      } 

       //Collections.sort(possibleOutputs); 
     }  
     //System.out.println(possibleOutputs); 
     Collections.sort(possibleOutputs); 
     //System.out.println(possibleOutputs); 
     return possibleOutputs.get(n); 
    } 

Answer 1

要求されたとして、ソリューションにあなたを導くの代わりに、あなたの厳密解を与える：

あなたが代わりに事実の後にそれをソートする、すでにソート順にセットu()を作成したいと思います。 Listではなく、Setを使用して、メンバーを簡単に複製せずに追加することができます。

最も効率的なソートセットは、BitSetです。 （1）セットで、それから...次の未処理のuのための

検索（x）の値uを初期化、およびへのu（2X + 1）とU（3X + 1）を追加することにより

スタートセット。

nextSetBitで次の未処理の値を検索するのは簡単です。

効率を上げるため、特定のポイントでu（x）値の生成を停止できます。学生に運動として残された正確な限界。