3
私はターゲットが供給された入力配列に起こる最小値と最大値のインデックスを検索するために必要な「探索範囲」と呼ばれる方法があります。
質問:
私は一度だけ入力をループしていますので、このソリューションの時間複雑性はO(n)のだと思います。私の理解は正しいのですか?
コード:
public class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums == null) {
return new int[2];
}
int min = -1, max = -1, l = nums.length;
int[] ans = new int[2];
for (int i = 0; i < l; i++) {
if (nums[i] == target) {
if (min == -1) {
min = i;
} else {
max = Math.max(i, max);
}
}
}
if (min != -1 && max == -1) {
max = min;
}
ans[0] = min;
ans[1] = max;
return ans;
}
}
EDIT
おかげで、私は今、上記のアルゴリズムの時間計算量はO(n)があることを知っています。私はO(logn)に向かって到達しようとしています。私は、最小および最大インデックスを発見するために、バイナリ検索の変種を使用しようとしました。このメソッドの時間複雑度は以下の通りですか?O(logn)?
public int[] searchRange(int[] nums, int target) {
if (nums == null)
return new int[2];
return searchRange(nums, target, 0, nums.length - 1);
}
public int[] searchRange(int[] nums, int target, int l, int h) {
int[] ans = new int[] { -1, -1 };
int middle = (l + h)/2;
if (l > h)
return ans;
if (nums[middle] == target) {
if (middle < nums.length - 1 && nums[middle + 1] == target) {
int[] right = searchRange(nums, target, middle + 1, h);
ans[1] = right[1];
ans[0] = middle;
}
if (middle >= 1 && nums[middle - 1] == target) {
int[] left = searchRange(nums, target, l, middle - 1);
ans[0] = left[0];
if (ans[1] == -1) {
ans[1] = middle;
}
}
if (ans[0] == ans[1] && ans[0] == -1) {
ans[0] = ans[1] = middle;
}
} else if (nums[middle] < target) {
return searchRange(nums, target, middle + 1, h);
} else {
return searchRange(nums, target, l, middle - 1);
}
return ans;
}
あなたの入力が-1より小さい負の数値で構成されているとどうなるか考えてください。 –
入力していないと思われます。 'target'がどこにあるのかの配列インデックスです。彼はターゲット番号の最初と最後のインデックスを記録しています。 '-1'は配列インデックスにとって不可能な値です。 – markspace
そのコードは機能しますか?あなたはそれをテストしましたか?バイナリ検索を行ってO(logn)に到達するという正しい考えがあります。 – jeromeyers