Question

1095. Find in Mountain Array

中文文档

Description

_(This problem is an interactive problem.)_

You may recall that an array arr is a mountain array if and only if:

• arr.length >= 3
• There exists some i with 0 < i < arr.length - 1 such that:
  • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given a mountain array mountainArr, return the minimum index such that mountainArr.get(index) == target. If such an index does not exist, return -1.

You cannot access the mountain array directly. You may only access the array using a MountainArray interface:

• MountainArray.get(k) returns the element of the array at index k (0-indexed).
• MountainArray.length() returns the length of the array.

Submissions making more than 100 calls to MountainArray.get will be judged _Wrong Answer_. Also, any solutions that attempt to circumvent the judge will result in disqualification.

 

Example 1:

Input: array = [1,2,3,4,5,3,1], target = 3
Output: 2
Explanation: 3 exists in the array, at index=2 and index=5. Return the minimum index, which is 2.

Example 2:

Input: array = [0,1,2,4,2,1], target = 3
Output: -1
Explanation: 3 does not exist in the array, so we return -1.

 

Constraints:

• 3 <= mountain_arr.length() <= 104
• 0 <= target <= 109
• 0 <= mountain_arr.get(index) <= 109

Solutions

Solution 1

# """
# This is MountainArray's API interface.
# You should not implement it, or speculate about its implementation
# """
# class MountainArray:
#  def get(self, index: int) -> int:
#  def length(self) -> int:


class Solution:
  def findInMountainArray(self, target: int, mountain_arr: 'MountainArray') -> int:
    def search(l: int, r: int, k: int) -> int:
      while l < r:
        mid = (l + r) >> 1
        if k * mountain_arr.get(mid) >= k * target:
          r = mid
        else:
          l = mid + 1
      return -1 if mountain_arr.get(l) != target else l

    n = mountain_arr.length()
    l, r = 0, n - 1
    while l < r:
      mid = (l + r) >> 1
      if mountain_arr.get(mid) > mountain_arr.get(mid + 1):
        r = mid
      else:
        l = mid + 1
    ans = search(0, l, 1)
    return search(l + 1, n - 1, -1) if ans == -1 else ans

/**
 * // This is MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface MountainArray {
 *   public int get(int index) {}
 *   public int length() {}
 * }
 */

class Solution {
  private MountainArray mountainArr;
  private int target;

  public int findInMountainArray(int target, MountainArray mountainArr) {
    int n = mountainArr.length();
    int l = 0, r = n - 1;
    while (l < r) {
      int mid = (l + r) >>> 1;
      if (mountainArr.get(mid) > mountainArr.get(mid + 1)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    this.mountainArr = mountainArr;
    this.target = target;
    int ans = search(0, l, 1);
    return ans == -1 ? search(l + 1, n - 1, -1) : ans;
  }

  private int search(int l, int r, int k) {
    while (l < r) {
      int mid = (l + r) >>> 1;
      if (k * mountainArr.get(mid) >= k * target) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return mountainArr.get(l) == target ? l : -1;
  }
}

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class MountainArray {
 *   public:
 *   int get(int index);
 *   int length();
 * };
 */

class Solution {
public:
  int findInMountainArray(int target, MountainArray& mountainArr) {
    int n = mountainArr.length();
    int l = 0, r = n - 1;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (mountainArr.get(mid) > mountainArr.get(mid + 1)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    auto search = [&](int l, int r, int k) -> int {
      while (l < r) {
        int mid = (l + r) >> 1;
        if (k * mountainArr.get(mid) >= k * target) {
          r = mid;
        } else {
          l = mid + 1;
        }
      }
      return mountainArr.get(l) == target ? l : -1;
    };
    int ans = search(0, l, 1);
    return ans == -1 ? search(l + 1, n - 1, -1) : ans;
  }
};

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * type MountainArray struct {
 * }
 *
 * func (this *MountainArray) get(index int) int {}
 * func (this *MountainArray) length() int {}
 */

func findInMountainArray(target int, mountainArr *MountainArray) int {
  n := mountainArr.length()
  l, r := 0, n-1
  for l < r {
    mid := (l + r) >> 1
    if mountainArr.get(mid) > mountainArr.get(mid+1) {
      r = mid
    } else {
      l = mid + 1
    }
  }
  search := func(l, r, k int) int {
    for l < r {
      mid := (l + r) >> 1
      if k*mountainArr.get(mid) >= k*target {
        r = mid
      } else {
        l = mid + 1
      }
    }
    if mountainArr.get(l) == target {
      return l
    }
    return -1
  }
  ans := search(0, l, 1)
  if ans == -1 {
    return search(l+1, n-1, -1)
  }
  return ans
}

/**
 * // This is the MountainArray's API interface.
 * // You should not implement it, or speculate about its implementation
 * class Master {
 *    get(index: number): number {}
 *
 *    length(): number {}
 * }
 */

function findInMountainArray(target: number, mountainArr: MountainArray) {
  const n = mountainArr.length();
  let l = 0;
  let r = n - 1;
  while (l < r) {
    const mid = (l + r) >> 1;
    if (mountainArr.get(mid) > mountainArr.get(mid + 1)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  const search = (l: number, r: number, k: number): number => {
    while (l < r) {
      const mid = (l + r) >> 1;
      if (k * mountainArr.get(mid) >= k * target) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return mountainArr.get(l) === target ? l : -1;
  };
  const ans = search(0, l, 1);
  return ans === -1 ? search(l + 1, n - 1, -1) : ans;
}

impl Solution {
  #[allow(dead_code)]
  pub fn find_in_mountain_array(target: i32, mountain_arr: &MountainArray) -> i32 {
    let n = mountain_arr.length();

    // First find the maximum element in the array
    let mut l = 0;
    let mut r = n - 1;

    while l < r {
      let mid = (l + r) >> 1;
      if mountain_arr.get(mid) > mountain_arr.get(mid + 1) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }

    let left = Self::binary_search(mountain_arr, 0, l, 1, target);

    if left == -1 {
      Self::binary_search(mountain_arr, l, n - 1, -1, target)
    } else {
      left
    }
  }

  #[allow(dead_code)]
  fn binary_search(m: &MountainArray, mut l: i32, mut r: i32, k: i32, target: i32) -> i32 {
    let n = m.length();

    while l < r {
      let mid = (l + r) >> 1;
      if k * m.get(mid) >= k * target {
        r = mid;
      } else {
        l = mid + 1;
      }
    }

    if m.get(l) == target {
      l
    } else {
      -1
    }
  }
}