ArrayList:整数のn番目のオカレンスを検索します

2015年09月08日に質問されました。  ·  閲覧回数 3.7k回  ·  ソース

Amit Kumar picture
2015年09月08日

ArrayListでn番目に出現する数値を見つける最良の方法は何ですか?

私はすでに何を知っていますか?

  1. lastIndexOf番号を見つけるために、ArrayListクラスに実装されているListインターフェイスにメソッドがあります。
  2. 最初の出現を見つけるために、 indexOfメソッドがあります。

私が何を解決していたのですか?

問題では、異なる番号のリストがあり、合計がターゲット番号に等しい2つの番号のインデックスを返す必要があります。 例: List = (1,2,1) & target = 2;これで、 1 + 1 =2と回答は、最初の1と2番目の1のインデックスになります。

注:私はこの問題を解決しました。上部の質問に答える必要があります。 ソリューションを確認する

私がしたこと?

  public static void main(String[] args)
  {
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(2);
    list.add(1);
    int length = list.size();
    int firstIndex = list.indexOf(1) + 1;
    int secondIndex = firstIndex + list.subList(firstIndex, length).indexOf(1) + 1;
    System.out.println(firstIndex);
    System.out.println(secondIndex);
  }

回答

Erwan C. picture
2015年09月08日
2

「すべて等しい数のリスト」-> {n、n、...、n、n}。

「合計がターゲット数に等しい最初の2つの数のインデックスを返す必要があります」target = xと仮定しましょう。 リストは同じ数でいっぱいなので、x / 2 = nの場合、インデックスは0と1になり、x / 2!= nの場合、一致するものはありません。


質問版の後


    int length=10;
    int target=100;
    int[] tab1= new int[length];
    Object[] tab2= new Object[length];
    Object[] tab2Sorted= new Object[length];

    for (int i = 0; i < tab2Sorted.length; i++) {
        for (int j = i; j < tab2Sorted.length; j++) {
            if(tab2Sorted[i]+tab2Sorted[j]==target){
                //do what you want on objects to get back indexes
            }

        }
        //As tab3 is sorted you dont have to read all the array
        if(tab2Sorted[i]>target/2){
            break;
        }
    }

tab2とtab2Sorted型をObjectからカスタム型に変更するだけで、intとそのインデックスを最初のタブから保存できます。

Diego Martinoia picture
2015年09月08日
1

リストがリストではなく配列であると仮定します(配列リストは、基本的に、ものの挿入が完了すると配列になります)。

また、合計がXになる最初の2つの数値のインデックスを検索するのではなく、2つの数値(存在する場合)だけを検索するとします。

O(n ^ 2)時間かかる簡単な解決策があります。この場合、各数値をその後に続くすべての数値で繰り返し、合計を確認します。

より良い方法は、配列をソートすることです(O(n * logn)を取ります)。 これで、各数値について、配列内でその補数、つまり、合計するとXになる数値のバイナリ検索を実行できます。これにはn(各数値)* log n(その補数のバイナリ検索)が必要です。 。

しかし、インデックスが必要なため、並べ替えることはできません。 それともできませんか?

値だけでなく、値とoriginalPositionのペアを格納する配列のコピーを作成するとどうなりますか。

class PosAndValue {
  public final int value;
  public final int pos;
  public PosAndValue(int v, int p) {
    value = v;
    pos = p;
  }
} 

これで、これらのPosAndValueの配列をその値で並べ替え、前述のアルゴリズムを実行してから、元の位置(つまり、インデックス)をすべてn * logn時間計算量(およびn空間計算量)で取得できます。

複雑さの点で、それほど「速く」することはできないと私はかなり確信しています。 これは、どのような場合でもコードが高速になることを意味するのではなく、十分に大きい入力(つまり、「十分に大きい」配列)の場合は高速になることに注意してください。 小さな入力の場合、例として、このすべてのオーバーヘッドによって実際にコードが遅くなる可能性があります。

入力の範囲が制限されていることがわかっていて、値に対してブールビットマップO(n)を実行すると、さらに改善できますが、これは指定されていない制約です。

Messer picture
2015年09月08日
1

あなたはこのようなものを作ることができます

List<Integer> numbers = new ArrayList<>(); // your list of numbers. Let's say it's {1, 1, 4, 5, 4}
numbers.add(1);
numbers.add(1);
numbers.add(4);
numbers.add(5);
numbers.add(4);
SparseArray<Set<Integer>> occurrences = new SparseArray<>();
for (int i = 0; i < numbers.size(); i++) {
    if (occurrences.indexOfKey(numbers.get(i)) < 0) {
        occurrences.put(numbers.get(i), new HashSet<Integer>());
    }
    Set<Integer> ints = occurrences.get(numbers.get(i)); // get current set
    ints.add(i); // add your new found one
    occurrences.put(numbers.get(i), ints); // put it back into your occurrences set
}

これにより、元の番号のSparseArrayと、元の配列リストからのこれらの番号の出現インデックスのセットが得られます。

{1=[1, 0], 4=[4, 2], 5=[3]}
OldCurmudgeon picture
2015年09月08日
1

これが最も効率的です。 配列のソートされたバージョン(元のオフセットへの参照を維持)とCollections.binarySearchを使用します。これにより、最高のパフォーマンスが得られます。

private Integer[] addsUp(List<Integer> numbers, int value) {
    // Hold the value and it's original offset.
    class No implements Comparable<No> {

        final int n;
        final int o;

        public No(int n, int o) {
            this.n = n;
            this.o = o;
        }

        public No(int n) {
            this(n, -1);
        }

        @Override
        public int compareTo(No o) {
            return Integer.compare(n, o.n);
        }

        @Override
        public String toString() {
            return "{" + n + " @ " + o + "}";
        }
    };
    // Build my list.
    List<No> myNumbers = new ArrayList(numbers.size());
    for (int i = 0; i < numbers.size(); i++) {
        myNumbers.add(new No(numbers.get(i), i));
    }
    // Start sorted.
    Collections.sort(myNumbers);
    // Upper limit of my search.
    int max;
    // Find the value in the numbers.
    No no = new No(value);
    int spot = Collections.binarySearch(myNumbers, no);
    // Did we find it?
    if (spot < 0) {
        // Not found - but this number is nearest to value.
        max = -spot - 1;
    } else {
        // Found ! No number higher than that is relevant.
        max = spot;
    }
    // For each start number.
    for (int first = 0; first < max; first++) {
        No remainder = new No(value - myNumbers.get(first).n);
        // Does that number appear in the list.
        int second = Collections.binarySearch(myNumbers, remainder);
        if (second >= 0) {
            // Found second number! Return original offsets.
            return new Integer[]{myNumbers.get(first).o, myNumbers.get(second).o};
        }
    }
    return null;
}

public void test() {
    List<Integer> numbers = Arrays.asList(1, 2, 1);
    Integer[] two = addsUp(numbers, 2);
    System.out.println("two = " + Arrays.toString(two));
    Integer[] three = addsUp(numbers, 3);
    System.out.println("three = " + Arrays.toString(three));
}
uoyilmaz picture
2015年09月08日
0

タイトルの質問については、ListのsubListメソッドと一緒にループを使用できます。

public static void main(String[] args)
{
    List<Integer> list = new ArrayList<Integer>();
    list.add(1);
    list.add(1);
    list.add(1);

    int n = 2;
    int index = -1;
    List<Integer> subList = list;

    for( int i = 0; i < n; i++)
    {
        index = subList.indexOf( 1);

        if( index == -1)
            break;

        System.out.println( i + "th index: " + index);
        subList = subList.subList( index+1, subList.size());
    }
}

実際の問題では、リスト内の番号のn番目の出現を見つけることは、それを行うための信頼できる方法ではありません。繰り返し配列要素がターゲット番号の約数であると想定しています。

McNultyyy picture
2015年09月08日
0
public static int nthIndexOf(List<Integer> list, int needle, int n){
    for (int i = 0; i < list.size(); i++) {
        if (list.get(i) == needle) {
            n--;
            if (n == 0) {
                return i;
            }
        }
    }
    return -1;
}

ジョンスキートへの小道具

developer picture
2015年09月08日
0
  public static void main(String[] args)
  {
    Integer[] numbersList = {1,2,3,4,5,6,7,8,9,10}; //Load your Array here
    List<Integer> list = Arrays.asList(numbersList);
    int targetNumber = 8;  //Load your targetNumber here

    int currrentVal = 0;
    int nextVal = 0;
    int i = 0;
    int j = 0;
    boolean found = false;
    for(i=0;i<list.size();i++) {
        currrentVal = list.get(i);          
        for(j=currrentVal+1;j<list.size();j++) {
            nextVal = list.get(j);              
            if(targetNumber == currrentVal+nextVal) {
                found = true;
                break;
            }
        }
        if(found) {
            break;
        }
    }
    if(found) {
        System.out.println("firstIndex  : "+i);
        System.out.println("secondIndex : "+j);
    } else {
        System.out.println(" No match found");
    }
  }