ดัชนีสูงสุดในอาร์เรย์ภูเขา


ระดับความยาก สะดวกสบาย
ถามบ่อยใน ไมโครซอฟท์
แถว การค้นหาแบบไบนารี

Peak Index ในปัญหา Mountain Array คืออะไร?

อาร์เรย์สามารถพูดได้ว่าเป็นไฟล์ อาร์เรย์ภูเขา หากแสดงคุณสมบัติต่อไปนี้:

  1. ความยาวของอาร์เรย์ที่กำหนดควรมากกว่าหรือเท่ากับ 3 ความยาว> = 3.
  2. สามารถมีองค์ประกอบสูงสุดหรือใหญ่ที่สุดในอาร์เรย์ได้เพียงองค์ประกอบเดียว
  3. ควรเป็นไปตาม: ARRAY [0] <ARRAY [1] <ARRAY [i-1] <ARRAY [i]> ARRAY [i + 1]> ARRAY [.. ]> ARRAY [length-1]

งานของเราคือการค้นหาดัชนีสูงสุดในภูเขา แถว.

ตัวอย่าง

อินพุต

[10, 20, 30, 20, 10]

เอาท์พุต

2

คำอธิบาย

ดัชนี "2" กล่าวคือ "30" มีค่ามากที่สุด

ดัชนีสูงสุดในอาร์เรย์ภูเขา

อินพุต

[0, 2, 1, 0]

เอาท์พุต

1

คำอธิบาย

ดัชนี "1" กล่าวคือ "2" มีค่ามากที่สุด

ขั้นตอนวิธี

  1. ตั้งค่าต่ำเป็น 0
  2. ตั้งค่าสูงเป็นความยาวของอาร์เรย์ลบ 1
  3. ประกาศตัวแปรกลาง
  4. ตั้งค่ากลาง = ต่ำ + (สูง - ต่ำ) / 2.
  5. ในขณะที่ต่ำ <สูง:
    1. ถ้า array [mid]> = array [mid + 1]
      1. สูง = กลาง
    2. อื่น
      1. จากนั้นต่ำ = กลาง + 1
  6. กลับต่ำ

คำอธิบาย

ดังนั้นเราต้องหาดัชนีสูงสุดในอาร์เรย์ที่กำหนด สำหรับสิ่งนี้เราจะใช้ไฟล์ ค้นหาไบนารี เข้าใกล้เล็กน้อย เรามีฟังก์ชั่นประกาศในรหัสของเราชื่อ getPeakIndex ซึ่งเราส่งอาร์เรย์อินพุตและความยาวของอาร์เรย์

เราประกาศกลางและเริ่มต้นเป็น 0 และสูงเท่ากับ high-1 เราจะเปิดไฟล์ ในขณะที่วนซ้ำ และจะคงอยู่จนกว่าจะเป็นเท็จเงื่อนไขต่ำ <high การเข้าสู่ลูปเราตั้งค่ากลาง = ต่ำ + (สูง - ต่ำ) / 2

ตัวอย่าง

ค่าอินพุตของเราคือ: {4,8,16,32,27,9,3};

ดังนั้นค่าสูงจะเป็นความยาวอาร์เรย์ -1 => 7 - 1 = 6

สูง = 6

ต่ำ = 0

กลาง = ต่ำ + (สูง - ต่ำ) / 2 => 0 + (6 - 0) / 2 = 3

กลาง = 3

ตอนนี้มันจะเป็น checwok if (array [mid]> = array [mid + 1])

กล่าวคือ 32 มากกว่าหรือเท่ากับ 27 เงื่อนไขจะเป็นจริงและตั้งค่าสูง = กลาง

ตอนนี้ต่ำ = 0

สูง = 3,

กลาง = 3;

กลาง = ต่ำ + (สูง - ต่ำ) / 2 => 0 + (3 - 0) / 2 = 1

กลาง = 1

ตอนนี้จะตรวจสอบว่า (array [mid]> = array [mid + 1])

กล่าวคือ 8 มากกว่าหรือเท่ากับ 16 เงื่อนไขจะเป็นเท็จและดำเนินการส่วนอื่นและตั้งค่าต่ำ = กลาง +1;

ตอนนี้ต่ำ = 2

สูง = 3,

กลาง = 1;

กลาง = ต่ำ + (สูง - ต่ำ) / 2 => 2 + (3 - 2) / 2 = 2

กลาง = 2

ตอนนี้จะตรวจสอบว่า (array [mid]> = array [mid + 1])

กล่าวคือ 16 มากกว่าหรือเท่ากับ 32 เงื่อนไขจะเป็นเท็จและดำเนินการส่วนอื่นและตั้งค่าต่ำ = กลาง +1;

ตอนนี้ต่ำ = 3

สูง = 3,

กลาง = 3;

และที่นี่เมื่อมันวนซ้ำในขณะที่ (ต่ำ <สูง) หมายถึง 3 <3 และเป็นเท็จ

และออกมาจากลูปและคืนค่าต่ำคือต่ำ = 3

และผลลัพธ์จะกลายเป็น:

ดัชนีสูงสุดคือ: 3

การใช้งานใน C ++

#include <iostream>
using namespace std;

int peakIndex(int arr[],int high)
{
    int low=0;
    int mid;
    high-=1;
    while( low < high )
    {
        mid = low +(high - low)/2;
        if(arr[mid]>=arr[mid+1])
        {
            high=mid;
        }
        else
        {
            low=mid+1;
        }
    }
    return low;
}
int main()
{
    int mountainArray[]= {4,8,16,32,27,9,3};
    int n = sizeof(mountainArray)/sizeof(mountainArray[0]);
    int peak=peakIndex(mountainArray,n);
    cout<<"Peak index is:"<<peak;
    return 0;
}
Peak index is:3

การใช้งานใน Java

class peakIndex {
  public static int getPeakIndex(int[] array) {
    int low = 0;
    int high = array.length - 1;
    int mid;
    while (low<high) {
      mid = low + (high - low) / 2;
      if (array[mid] >= array[mid + 1]) {
        high = mid;
      } else {
        low = mid + 1;
      }
    }
    return low;
  }

  public static void main(String[] args) {
    peakIndex pi = new peakIndex();
    int mountainArray[] = { 4, 8, 16, 32, 27, 9, 3 };
    int peak = getPeakIndex(mountainArray);
    System.out.println("Peak index is:" + peak);
  }
}
Peak index is:3

การวิเคราะห์ความซับซ้อน

ความซับซ้อนของเวลา

O (บันทึก n) โดยที่ n คือความยาวของอาร์เรย์

ความซับซ้อนของอวกาศ

O (1) เนื่องจากเราไม่ได้ใช้พื้นที่พิเศษหรือพื้นที่เสริมในการประเมิน

อ้างอิง