یافتن شاخص اوج در یک آرایه کوه

سلام دوستان من! امیدوارم همه شما عالی کار کنید. امروز ، مشکل پیدا کردن یک عنصر اوج در یک آرایه کوه را حل خواهیم کرد.

در اینجا ارسال من در LeetCode است.

عنصر اوج چیست؟

یک عنصر اوج در یک آرایه عنصری است که از هر دو همسایه خود بزرگتر است. اگر آرایه کنید ، به سادگی قرار دهید[i] اوج است ، پس:

array[i - 1] < array[i] && array[i] > array[i + 1]

برای بهینه سازی جستجو ، من از جستجوی باینری برای حفظ پیچیدگی زمان کارآمد ، حرکت به چپ یا راست بر اساس مقدار متوسط ​​استفاده می کنم.

1. لبه: اگر طول آرایه 1 یا کمتر باشد (array.length <= 1) ، ما شاخص 0 را برمی گردانیم.
2. لبه: اگر عنصر اول از قسمت بعدی بیشتر باشد (array[0] > array[1]) ، ما 0 را برمی گردانیم ، زیرا اولین فهرست شاخص اوج است.
3. لبه: اگر آخرین عنصر بیشتر از حالت قبلی باشد (array[array.length - 1] > array[array.length - 2]) ، ما Array.L طول – 1 را برمی گردانیم ، زیرا آخرین عنصر اوج است.
4. حال ، اگر آرایه[mid – 1] <آرایه[mid] && آرایه[mid] > آرایه[mid + 1]، ما در اواسط باز می گردیم ، زیرا این عنصر اوج است ، از همسایگان خود بزرگتر است.
5. دیگری اگر: آرایه[mid] > آرایه[mid – 1]، ما از آرایه درست حرکت می کنیم[mid] بیشتر از عنصر چپ است ، به این معنی که قله در سمت راست نهفته است.
6. دیگری: ما به سمت چپ حرکت می کنیم ، زیرا اواسط بیشتر از عنصر مناسب است.

بیایید کد کنیم

من برای یافتن عنصر اوج و اجرای جستجوی باینری برای یک راه حل بهینه شده ، در JavaScript کد می کنم.

var findPeakElement = function (nums) {
  let length = nums.length;

  if (1 >= length) {
    return 0;
  }

  if (nums[0] > nums[1]) {
    return 0;
  }

  if (nums[length - 1] > nums[length - 2]) {
    return length - 1;
  }

  let left = 1;
  let right = length - 2;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);

    if (nums[mid - 1] < nums[mid] && nums[mid] > nums[mid + 1]) {
      return mid;
    } else if (nums[mid] > nums[mid - 1]) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
};

برخی از آزمون ها را اجرا کنید:

console.log(findPeakElement([1, 2, 3, 1])); // Index: 2, Element: 3
console.log(findPeakElement([1, 2, 1, 3, 5, 6, 4])); // Index: 5, Element: 6
console.log(findPeakElement([1])); // Index: 0, Element: 1
console.log(findPeakElement([3, 4, 3, 2, 1])); // Index: 1, Element: 4

می توانید این مشکل را امتحان کنید: leetcode

با تشکر از خواندن