[LeetCode] 034.範囲の検索(中)(C ++ / Java)
034 Search
インデックス: [LeetCode]問題インデックスのLeetcodeソリューション(C ++ / Java / Python / Sql)
Github: https://github.com/illuz/leetcode
035.範囲の検索(中)
リンク :
トピック: https://leetcode.com/problems/search-for-a-range/
コード(github): https://github.com/illuz/leetcode
問題の意味 :
順序付けられた配列で数値の範囲を見つけます。 (何度か繰り返されるため)
分析 :
または二分探索が変形しました。
- (C ++) C ++ STLの直接使用
lower_bound
upper_bound
で怠惰になります。 - (Java) 普通から半分に変えてください。
コード :
C ++:
class Solution { public: vector searchRange(int A[], int n, int target) { int* lower = lower_bound(A, A + n, target) int* upper = upper_bound(A, A + n, target) if (*lower != target) return vector {-1, -1} else return vector{lower - A, upper - A - 1} } }
Java:
public class Solution { public int[] searchRange(int[] A, int target) { int[] ret = new int[2] ret[0] = ret[1] = -1 int left = 0, right = A.length - 1, mid while (left <= right) { if (A[left] == target && A[right] == target) { ret[0] = left ret[1] = right break } mid = (right + left) / 2 if (A[mid] target) { right = mid - 1 } else { if (A[right] == target) { ++left } else { --right } } } return ret } }