アルゴリズム探求-隣接している元素の位置を求めよう

問題

U < V < WまたはU > V > Wの時、整数VとUはWの間にある。

開いていない配列Aは与えられたN個の整数で構成されていて、数字のインデックス(P,Q)のペアは0 ≤ P < Q < Nの隣接する数がA[P]とA[Q]の間にないことと、A[P]≠A[Q]であることを表す。

例えば、配列Aでは:

A[0] = 0
A[1] = 3
A[2] = 3
A[3] = 7
A[4] = 5
A[5] = 3
A[6] = 11
A[7] = 1

次のインデックスのペアは隣接した値を持っている。

(0,7), (1,4), (1,7), (2,4), (2,7), (3,4), (3,6), (4,5), (5,7)

例えば、インデックス4と5は隣接した数字を持っている。なぜなら、A[4] = 5とA[5] = 3は異なっていて、配列Aにはその間に挟まる数字はない。つまり、数字4のみが間にあるが、配列には存在しない。

与えられた二つのインデックスPとQの距離はX ≥ 0ではabs(X) = X、X < 0ではabs(X) = -Xの時、abs(P-Q)として定義される。例えば、インデックス4と5の中の距離は1であり、その理由はabs(4-5) = (5-4) = 1だからである。

関数を作成せよ:

class Solution { public int solution{int[] A); }

与えられた、空いていない配列AはN個の整数で構成されていて、隣接した値を持っている配列の一番遠い距離をリターンする。この関数は隣接したインデックスがない場合、-1をリターンしなければならない。

例えば、与えられた配列Aは次のようになる。

A[0] = 1
A[1] = 4
A[2] = 7
A[3] = 3
A[4] = 3
A[5] = 5

この関数は次の理由で4をリターンしなければならない:

  • インデックス0と4は隣接している。その理由はA[0] ≠ A[4]で、配列にはA[0] = 1とA[4] = 3の間の数字を持っていないからだ。
  • これらのインデックスの距離はabs(0-4) = 4である。
  • より遠い距離の隣接したインデックスのペアはない。

次のように仮定する:

  • Nは[1..40,000]の範囲内である。
  • 配列Aの項目は整数であり、範囲[-2,147,483,648..2,147,483,647]の内である。

複雑さ:

  • 期待される最悪の場合、時間計算量はO(N*log(N))である。
  • 期待される最悪の場合、空間計算量はO(N)で、入力空間以降を言う。(インプット記号に必要な空間を除く)

発送

  • 左から探してその次の隣接した数を探すのは?
    • N個の項目に対し、N-1個のリピートをしなければならない。
    • よりいい方法があるはずだ。
  • ソートを先にした後に、低い順で登りながら当ててみるか?
    • ソートアルゴリズムは検証済みであり、内部のライブラリの方が速いし、信用できる。
    • 同じ数を除くとループはさらに速くなる。
    • でも、ソート後インデックスがなくなるのでは?
      • 元の位置は左から探すなど原始的な方法でいい。
      • 見つかったとたん、脱出するとループは短くなる。

解き方

import java.util.ArrayList;
import java.util.Arrays;

public class Question {

    /*プロゴラムのエントリ。*/
   public static void main(String[] args) {
      // TODO Auto-generated method stub
      //int[] A = new int[] {0,3,3,7,5,3,11,1};
      //int[] A = new int[] {1,4,7,3,3,5};
      //int[] A = new int[] {1,1,1,1,1,1,1,1};
      
      //ランダムの40000個の整数を入れる
      int[] A = new int[40000];
      for(int i = 0; i < A.length; i++) {
         A[i]=(int)Math.round(Math.random()*2147483647*2-2147483647);
      }
      
      //時間の計算
      long startTime = System.nanoTime();
      System.out.println("Result: "+solution(A));
      System.out.println("Elapsed Time: "+(System.nanoTime()-startTime)/1000000.0+"ms");
   }
   /* */

   /* 補助関数: 配列から項目の位置を探す */
   private static int indexOfArray(int[] A, int val, boolean reverse) {
      if(reverse) {
         //後ろから
         for(int i = A.length-1; i >= 0; i--) {
            if(A[i]==val) {
               return i;
            }
         }
      } else {
         //前から
         for(int i = 0; i < A.length; i++) {
            if(A[i]==val) {
               return i;
            }
         }
      }
      return -1;
   }
   
   /* minと maxを配列でindexOfArrayを使い、それぞれ求めてその最大値を求める */
   private static int findPairDistance(int[] A, int min, int max) {
      //左、右からmin, max検索
      int aleft = indexOfArray(A,min,false);
      int aright = indexOfArray(A,min,true);
      int bleft = indexOfArray(A,max,false);
      int bright = indexOfArray(A,max,true);
      return Math.max(Math.abs(aleft-bright),Math.abs(aright-bleft));
   }
   
   /* ソリューションのメイン */
   public static int solution(int[] A) {
      //ソート後重複を除く
      int[] sorted = A.clone();
      Arrays.sort(sorted);
      /*for(int i = 0; i < sorted.length; i++) {
         System.out.print(sorted[i]+",");
      }*/
      //ArrayList alSel = new ArrayList<>();
      int max = -1;
      for(int i = 1;i < sorted.length; i++) {
         //前項と現在項の違い
         int cha = sorted[i]-sorted[i-1];
         if(cha >= 1) { //違いが1以上の場合整数は変化したとする
            //alSel.add(sorted[i-1]);
            //findPairDistance(A,A[i-1],A[i]);
            max = Math.max(max, findPairDistance(A,sorted[i-1],sorted[i]));
            //二つの左右検索最大距離を求めた後、maxより大きい時に記録
            //System.out.println(String.format("Value: (%d,%d), Distance: %d",sorted[i-1],sorted[i],findPairDistance(A,sorted[i-1],sorted[i])));
         }
      }
      
      
      return max;
   }

}

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です