diff options
author | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
---|---|---|
committer | jack <[email protected]> | 2024-06-14 13:13:15 -0600 |
commit | d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch) | |
tree | 96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /find_peak_element.c | |
download | leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip |
initial
Diffstat (limited to 'find_peak_element.c')
-rw-r--r-- | find_peak_element.c | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/find_peak_element.c b/find_peak_element.c new file mode 100644 index 0000000..9803f70 --- /dev/null +++ b/find_peak_element.c @@ -0,0 +1,45 @@ +// 162. Find Peak Element +#include "leetcode.h" + +/* + * a peak element is an element that is strictly greater than its neighbours. + * given a 0 indexed array 'nums', find a peak element and return its index. if + * the array contains multiple peaks, return the index to any of the peaks. you + * may imagine that 'nums[-1] = nums[n] = -inf' in other words, an element is + * always considered to be strictly greater than a neighbour that is outside the + * array. you must write an algorithm that runs in 'O(log n)' time. + */ + +int findPeakElement(int *nums, int numsSize) { + if (numsSize == 1) + return 0; + if (numsSize == 2) + return nums[0] > nums[1] ? 0 : 1; + int left = 0, right = numsSize - 1, mid; + while (left < right) { + mid = (left + right) / 2; + if (!mid) + break; + if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) + return mid; + else if (nums[mid] > nums[mid - 1]) + left = mid + 1; + else + right = mid - 1; + } + if (right < numsSize - 1 && right) { + if (nums[right] > nums[right + 1] && nums[right] > nums[right - 1]) + return right; + } else if (left < numsSize - 1 && left) { + if (nums[left] > nums[left + 1] && nums[left] > nums[left - 1]) + return left; + } else + return !left ? left : right; + return 0; +} + +int main() { + int n1[] = {1, 2, 3, 1}, n2[] = {1, 2, 1, 3, 5, 6, 4}; + printf("%d\n", findPeakElement(n1, ARRAY_SIZE(n1))); // expect: 2 + printf("%d\n", findPeakElement(n2, ARRAY_SIZE(n2))); // expect: 5 +} |