[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



問題の意味

順序付けられた配列で数値の範囲を見つけます。 (何度か繰り返されるため)

分析

または二分探索が変形しました。



  1. (C ++) C ++ STLの直接使用lower_bound upper_boundで怠惰になります。
  2. (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 } }