範囲内のすべての値が配列内に存在するかどうかを確認する最良の方法は何ですか？ （Java）

Question

1,2,3、... nの各値が順序付けられていないint配列にあるかどうかを判断する作業があります。私はこれが最も効率的な方法であるかどうかは分かりませんが、range [i]（range [0] = 1）の順番で1-nからすべての数字を持つrangeというint []を作成しました、range [1] = 2、ect）。次に、containsAllメソッドを使用して、指定された数値の配列に範囲配列のすべての数値が含まれているかどうかを確認しようとしました。しかし、私がこれをテストすると、falseを返します。私のコードに何が問題なのですか？この問題を解決するための効率的な方法は何でしょうか？

public static boolean hasRange(int [] givenNums, int[] range) { 
    boolean result = true; 
    int n = range.length; 
    for (int i = 1; i <= n; i++) { 
    if (Arrays.asList(givenNums).containsAll(Arrays.asList(range)) == false) { 
      result = false; 
    } 
    } 
    return result; 
} 

（私は私はかなりのcontainsAllメソッドを使用するよりも、手動でこれを行うことになってるかなり確信しているので、誰もがそれをそれが特に有用であろうそのように解決する方法を知っていれば！）

ここです好奇心を抱く人にはこの方法が関係します。

public static void checkMatrix(int[][] intMatrix) { 
    File numberFile = new File("valid3x3") ; 
    intMatrix= readMatrix(numberFile); 
    int nSquared = sideLength * sideLength; 
    int[] values = new int[nSquared]; 
    int[] range = new int[nSquared]; 
    int valCount = 0; 

    for (int i = 0; i<sideLength; i++) { 
     for (int j=0; j<sideLength; j++) { 

      values[valCount] = intMatrix[i][j]; 
      valCount++; 
     } 
    } 

    for (int i=0; i<range.length; i++) { 
     range[i] = i+1; 
    } 

    Boolean valuesThere = hasRange(values, range); 

値は印刷時に偽です。

Answer 1

あなたは1次元配列を持っているといいますか？ 良いそれから、あなたは複雑に思っています。 私は配列のすべての数字が番号順であるかどうかを調べる別の方法を説明しようとします。あなたは、配列をすることができます。このループをやった後、すべての

int[] array = {9,4,6,7,8,1,2,3,5,8}; 

まずあなたが

Arrays.sort(array); 

とアレイsimpelを注文することができます。

は、たとえば次のような値を持つ配列を持っています

for(int i = array[0];i < array.length; i++){ 
    if(array[i] != i) return false; 

Answer 2

この問題を解決する方法の1つは、あなたが言ったように、ソートされていないint配列をソートして、バイナリ検索を実行して、1 ... nのすべての値を探します。申し訳ありませんがJavaに慣れていないので、私は擬似コードで書きました。 O（N）を取る線形検索の代わりに、バイナリ検索はO（logN）で実行されるので、はるかに高速です。しかし、前提条件はあなたが検索している配列をソートする必要があります。

//pseudocode 
int range[N] = {1...n}; 
cnt = 0; 
while(i<-inputStream) 
int unsortedArray[cnt]=i 
cnt++; 

sort(unsortedArray); 

for(i from 0 to N-1) 
{ 
    bool res = binarySearch(unsortedArray, range[i]); 
    if(!res) 
    return false; 
} 

return true;

Answer 3

私があなたの説明から理解しているのは、配列が必ずしもソートされているわけではないということです。だから、私たちはlinear searchメソッドを使ってみることができます。

public static void main(String[] args){ 
    boolean result = true; 
    int[] range <- Contains all the numbers 
    int[] givenNums <- Contains the numbers to check 
    for(int i=0; i<givenNums.length; i++){ 
     if(!has(range, givenNums[i])){ 
      result = false; 
      break; 
     } 
    } 
    System.out.println(result==false?"All elements do not exist":"All elements exist"); 
} 

private static boolean has(int[] range, int n){ 
    //we do linear search here 
    for(int i:range){ 
     if(i == n) 
     return true; 
    } 
    return false; 
} 

このコードは、配列givenNums内のすべての要素がアレイrangeに存在するかどうかを表示します。

Answer 4

数学的アプローチ：最大値を知っている場合（または最大値を検索する場合）、合計を確認してください。 1,2,3、...、nの合計は常にn *（n + 1）/ 2に等しいためです。したがって、合計がその式に等しい場合、すべての値が配列内にあり、そうでない場合、一部の値が欠落しています。その後

if (condition == false) // Works, but at the end you have if (true == false) or such 
if (!condition) // Better: not condition 

// Do proper usage, if you have a parameter, do not read it in the method. 
File numberFile = new File("valid3x3") ; 
intMatrix = readMatrix(numberFile); 
checkMatrix(intMatrix); 

public static void checkMatrix(int[][] intMatrix) { 
    int nSquared = sideLength * sideLength; 
    int[] values = new int[nSquared]; 

問題：例

public class NewClass12 { 
    static int [] arr = {1,5,2,3,4,7,9,8}; 
    public static void main(String [] args){ 
     System.out.println(containsAllValues(arr, highestValue(arr))); 
    } 

    public static boolean containsAllValues(int[] arr, int n){   
     int sum = 0;   
     for(int k = 0; k<arr.length;k++){ 
      sum +=arr[k]; 
     } 
     return (sum == n*(n+1)/2); 
    } 

    public static int highestValue(int[]arr){ 
     int highest = arr[0]; 
     for(int i = 0; i < arr.length; i++) { 
      if(highest<arr[i]) highest = arr[i]; 
     } 
     return highest; 
    } 
} 

は、これに応じて、あなたの方法は、この

public static boolen hasRange (int [] arr){ 
    int highest = arr[0]; 
    int sum = 0; 
    for(int i = 0; i < arr.length; i++) { 
      if(highest<arr[i]) highest = arr[i]; 
    } 
    for(int k = 0; k<arr.length;k++){ 
      sum +=arr[k]; 
    } 
    return (sum == highest *(highest +1)/2); 
} 

Answer 5

まずスタイルのようになります。 Listやもっと良いSetのアプローチは正確な抽象レベルであることがわかります。細部までは分かりません。しかしここでそれが求められています。

[1、...、n]の範囲内のすべての要素が存在するかどうかを知ること。

• あなたは、与えられた数字を歩く
• 、すべての数の可能性は、それが範囲内の新しい、もはや新しい、

• として、新たな数字に達したn個あれば、それをマークするかどうかを見て：trueを返します。

  int newRangeNumbers = 0; 
  boolean[] foundRangeNumbers = new boolean[n]; // Automatically false 
  

より良い名前を考えます。

Answer 6

Arrays.asList(givenNums). 

これはあなたの意見ではありません。単一の要素を持つList<int[]>を返します。givenNumsからIntegerに値を入れず、List<Integer>を返します。これは、あなたのアプローチがうまくいかない理由を説明します。

Java 8ストリームを使用して、givensを永続的に並べ替えたくないと仮定します。あなたが気にしない場合copyOf()を排除：

int[] sorted = Arrays.copyOf(givens,givens.length); 
    Arrays.sort(sorted); 
    boolean result = Arrays.stream(range).allMatch(t -> Arrays.binarySearch(sorted, t) >= 0); 

Answer 7

public static boolean hasRange(int [] givenNums, int[] range) { 
    Set result = new HashSet(); 

    for (int givenNum : givenNums) { 
     result.add(givenNum); 
    } 

    for (int num : range) { 
     result.add(num); 
    } 

    return result.size() == givenNums.length; 
} 

Answer 8

あなたのコードの問題は、機能hasRangeは、2つの基本int配列を取り、あなたがArrays.asListにプリミティブint型の配列を渡すとき、それはListを含む返すことですタイプint[]の単一要素。この中でcontainsAllは、実際の要素をチェックするのではなく、プリミティブ配列オブジェクト参照を比較します。

ソリューションは、あなたがInteger[]を作成し、Arrays.asListを使用するか、それが不可能な場合、その後int[]はInteger[]に変換のいずれかです。

public static boolean hasRange(Integer[] givenNums, Integer[] range) { 
    return Arrays.asList(givenNums).containsAll(Arrays.asList(range)); 
} 

サンプルコードと出力については、hereを確認してください。

ApacheCommonsLangライブラリを使用している場合は、int[]をInteger[]に直接変換することができます。 Integer[] newRangeArray = ArrayUtils.toObject(range);