Java에서 이분법을 구현하는 방법
- WBOY앞으로
- 2023-05-03 10:04:06776검색
정렬 배열에서 특정 숫자가 존재하는지 알아보세요
아이디어:
정렬 배열이므로 먼저 중간점 위치를 구하고, 중간점은 배열을 왼쪽으로 나눌 수 있습니다. 그리고 오른쪽 절반.
중점 위치 값이 목표 값과 같을 경우 중간점 위치를 직접 반환합니다.
중간점 위치의 값이 목표값보다 작은 경우 배열의 중간점을 기준으로 왼쪽으로 가서 같은 방법으로 검색합니다.
중간점 위치의 값이 목표값보다 큰 경우 배열의 중간점의 오른쪽을 잡아 같은 방법으로 검색합니다.
끝까지 찾을 수 없으면 -1을 반환합니다.
Code
class Solution {
public int search(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return -1;
}
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (arr[m] == t) {
return m;
} else if (arr[m] > t) {
r = m - 1;
} else {
l = m + 1;
}
}
return -1;
}
}시간 복잡도 O(logN). O(logN)。
在一个有序数组中，找大于等于某个数最左侧的位置
示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2
说明：如果要在num这个数组中插入 5 这个元素，应该是插入在元素 3 和 元素 5 之间的位置，即 2 号位置。
示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1
说明：如果要在num这个数组中插入 2 这个元素，应该是插入在元素 1 和 元素 3 之间的位置，即 1 号位置。
示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4
说明：如果要在num这个数组中插入 7 这个元素，应该是插入在数组末尾，即 4 号位置。
通过上述示例可以知道，这题本质上就是求在一个有序数组中，找大于等于某个数最左侧的位置，如果不存在，就返回数组长度（表示插入在最末尾位置）
我们只需要在上例基础上进行简单改动即可，上例中，我们找到满足条件的位置就直接return了
if (arr[m] == t) {
return m;
}在本问题中，因为要找到最左侧的位置，所以，在遇到相等的时候，只需要先把位置记录下来，不用直接返回，然后继续去左侧找是否还有满足条件的更左边的位置。
同时，在遇到arr[m] > t条件下，也需要记录下此时的m位置，因为这也可能是满足条件的位置。
代码：
class Solution {
public static int searchInsert(int[] arr, int t) {
int ans = arr.length;
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l)>>1);
if (arr[m] >= t) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
}整个算法的时间复杂度是O(logN)。
在排序数组中查找元素的第一个和最后一个位置
思路
本题也是用二分来解，当通过二分找到某个元素的时候，不急着返回，而是继续往左（右）找，看能否找到更左（右）位置匹配的值。
代码如下：
class Solution {
public static int[] searchRange(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return new int[]{-1, -1};
}
return new int[]{left(arr,t),right(arr,t)};
}
public static int left(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return -1;
}
int ans = -1;
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (arr[m] == t) {
ans = m;
r = m - 1;
} else if (arr[m] < t) {
l = m +1;
} else {
// arr[m] > t
r = m - 1;
}
}
return ans;
}
public static int right(int[] arr, int t) {
if (arr == null || arr.length < 1) {
return -1;
}
int ans = -1;
int l = 0;
int r = arr.length - 1;
while (l <= r) {
int m = l + ((r - l) >> 1);
if (arr[m] == t) {
ans = m;
l = m + 1;
} else if (arr[m] < t) {
l = m +1;
} else {
// arr[m] > t
r = m - 1;
}
}
return ans;
}
}时间复杂度 O(logN)。
局部最大值问题
思路
假设数组长度为N，首先判断0号位置的数和N-1位置的数是不是峰值位置。
0号位置只需要和1号位置比较，如果0号位置大，0号位置就是峰值位置，可以直接返回。
N-1号位置只需要和N-2号位置比较，如果N-1号位置大，N-1号位置就是峰值位置，可以直接返回。
如果0号位置和N-1在上轮比较中均是最小值，那么数组的样子必然是如下情况：
由上图可知，[0..1]区间内是增长趋势, [N-2...N-1]区间内是下降趋势。
那么峰值位置必在[1...N-2]之间出现。
此时可以通过二分来找峰值位置，先来到中点位置，假设为mid，如果中点位置的值比左右两边的值都大:
arr[mid] > arr[mid+1] && arr[mid] > arr[mid-1]
则mid位置即峰值位置，直接返回。
否则，有如下两种情况：
情况一：mid 位置的值比 mid - 1 位置的值小
趋势如下图：
则在[1...(mid-1)]
예 1:
Input: nums = [1,3,5,6], target = 5
num을 사용하려면 이 배열에 삽입된 요소 5는 요소 3과 요소 5 사이, 즉 위치 2에 삽입되어야 합니다. 🎜🎜예제 2:🎜🎜입력: nums = [1,3,5,6], target = 2🎜🎜출력: 1🎜🎜설명: num 배열에 2를 삽입하려는 경우 요소는 요소 1과 요소 3 사이, 즉 위치 1에 삽입되어야 합니다. 🎜🎜예 3:🎜🎜입력: nums = [1,3,5,6], target = 7🎜🎜출력: 4🎜🎜설명: num 배열에 7을 삽입하려는 경우 요소는 배열의 끝, 즉 위치 4에 삽입되어야 합니다. 🎜🎜위의 예를 보면 이 질문의 본질은 순서 배열에서 특정 숫자보다 크거나 같은 가장 왼쪽 위치를 찾는 것임을 알 수 있습니다. 존재하지 않으면 배열의 길이를 반환합니다(표시). 마지막 위치에 삽입됨)🎜🎜위 예시를 토대로 간단한 변경만 하면 됩니다. 위 예시에서는 조건에 맞는 위치를 찾으면 바로 return🎜public class LeetCode_0162_FindPeakElement {
public static int findPeakElement(int[] nums) {
if (nums.length == 1) {
return 0;
}
int l = 0;
int r = nums.length - 1;
if (nums[l] > nums[l + 1]) {
return l;
}
if (nums[r] > nums[r - 1]) {
return r;
}
l = l + 1;
r = r - 1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
return mid;
}
if (nums[mid] < nums[mid + 1]) {
l = mid + 1;
} else if (nums[mid] < nums[mid - 1]) {
r = mid - 1;
}
}
return -1;
}
}🎜 이 질문에서는 가장 왼쪽 위치를 찾아야 하므로동등할 때 직접 반환하지 않고 먼저 위치만 기록한 다음 계속해서 왼쪽으로 이동하여 위치가 있는지 확인하면 됩니다. 조건을 충족하는 왼쪽 위치입니다. 🎜🎜동시에 arr[m] > t가 나타나면 m 위치도 기록해야 합니다. 조건을 만족하는 곳이기도 합니다. 🎜🎜코드: 🎜rrreee🎜전체 알고리즘의 시간 복잡도는 O(logN)입니다. 🎜🎜정렬된 배열에서 요소의 첫 번째 위치와 마지막 위치 찾기🎜🎜🎜🎜Thinking🎜🎜이 질문도 이분법으로 해결됩니다. 이분법을 통해 요소가 발견되면 서두르지 말고 계속해서 왼쪽(오른쪽)으로 검색하여 찾을 수 있는지 확인하세요. more 왼쪽(오른쪽) 위치와 일치시킬 값입니다. 🎜🎜코드는 다음과 같습니다: 🎜rrreee🎜시간 복잡도 O(logN). 🎜🎜로컬 최대 문제🎜🎜🎜🎜 아이디어 🎜🎜 배열의 길이가 N이라고 가정하고, 먼저 0 위치에 있는 숫자와 N-1에 있는 숫자가 있는지 확인하세요. > 위치는 피크 위치입니다. 🎜🎜0 위치는 1 위치와 비교하면 됩니다. 0 위치가 더 크면 0 code> position 피크 위치이며 직접 반환될 수 있습니다. 🎜🎜<code>N-1 위치는 N-2 위치와 비교하면 됩니다. N-1 위치가 더 큰 경우 N Position -1은 피크 위치이며 직접 반환될 수 있습니다. 🎜🎜마지막 비교 라운드에서 0 위치와 N-1이 모두 최소값인 경우 배열은 다음과 같아야 합니다. 🎜🎜🎜🎜위 그림에서 볼 수 있듯이, [0..1 ]간격은 증가 추세이고, [N-2...N-1]간격은 하락 추세입니다. 🎜🎜그러면 피크 위치는 [1...N-2] 사이에 나타나야 합니다. 🎜🎜이때, 이등분을 통해 정점 위치를 찾을 수 있습니다. 먼저 중간점 위치의 값이 더 크다면 중간이라고 가정하고 중간점 위치로 이동합니다. 왼쪽과 오른쪽 값보다 :🎜rrreee🎜 mid 위치가 피크 위치로 바로 반환됩니다. 🎜🎜그렇지 않으면 다음과 같은 두 가지 상황이 있습니다. 🎜🎜사례 1: mid 포지션의 가치가 mid-1 포지션의 가치보다 작습니다. 🎜🎜추세는 다음과 같습니다. 🎜🎜
🎜🎜은 [1...(mid- 1)] 간격 두 포인트. 🎜🎜사례 2: 중간 위치의 가치가 중간 + 1 위치의 가치보다 작습니다🎜🎜 추세는 다음과 같습니다. 🎜🎜🎜🎜则在[(mid+1)...(N-2)]区间内继续上述二分。
完整代码
public class LeetCode_0162_FindPeakElement {
public static int findPeakElement(int[] nums) {
if (nums.length == 1) {
return 0;
}
int l = 0;
int r = nums.length - 1;
if (nums[l] > nums[l + 1]) {
return l;
}
if (nums[r] > nums[r - 1]) {
return r;
}
l = l + 1;
r = r - 1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (nums[mid] > nums[mid + 1] && nums[mid] > nums[mid - 1]) {
return mid;
}
if (nums[mid] < nums[mid + 1]) {
l = mid + 1;
} else if (nums[mid] < nums[mid - 1]) {
r = mid - 1;
}
}
return -1;
}
}时间复杂度O(logN)。
위 내용은 Java에서 이분법을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!