問題
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;
}
}