三分答案
三分答案
问题描述
三分答案是一种用于查找单峰/单谷函数极值的搜索算法。通过将区间分成三份,比较两个三分点的函数值来确定极值的位置。
整数三分
算法思想
- 确定答案的取值范围[left, right)
- 取两个三分点 mid1 和 mid2
- 比较两点函数值确定搜索方向
- 每次排除三分之一的区间
代码实现
class Solution {
public:
int getValue(vector<int>& nums, int x) {
// 计算在位置x处的函数值
int value = 0;
for (int i = 0; i < nums.size(); i++) {
value += abs(nums[i] - x);
}
return value;
}
int findMin(vector<int>& nums) {
int left = *min_element(nums.begin(), nums.end());
int right = *max_element(nums.begin(), nums.end()) + 1;
while (right - left >= 3) {
int len = right - left;
int mid1 = left + len / 3;
int mid2 = right - len / 3;
if (getValue(nums, mid1) < getValue(nums, mid2)) {
right = mid2;
} else {
left = mid1;
}
}
// 暴力查找最后几个点
int minValue = INT_MAX, ans = left;
for (int i = left; i < right; i++) {
int value = getValue(nums, i);
if (value < minValue) {
minValue = value;
ans = i;
}
}
return ans;
}
};
class Solution {
private int getValue(int[] nums, int x) {
// 计算在位置x处的函数值
int value = 0;
for (int num : nums) {
value += Math.abs(num - x);
}
return value;
}
public int findMin(int[] nums) {
int left = Arrays.stream(nums).min().getAsInt();
int right = Arrays.stream(nums).max().getAsInt() + 1;
while (right - left >= 3) {
int len = right - left;
int mid1 = left + len / 3;
int mid2 = right - len / 3;
if (getValue(nums, mid1) < getValue(nums, mid2)) {
right = mid2;
} else {
left = mid1;
}
}
// 暴力查找最后几个点
int minValue = Integer.MAX_VALUE, ans = left;
for (int i = left; i < right; i++) {
int value = getValue(nums, i);
if (value < minValue) {
minValue = value;
ans = i;
}
}
return ans;
}
}
class Solution:
def getValue(self, nums: List[int], x: int) -> int:
# 计算在位置x处的函数值
return sum(abs(num - x) for num in nums)
def findMin(self, nums: List[int]) -> int:
left = min(nums)
right = max(nums) + 1
while right - left >= 3:
length = right - left
mid1 = left + length // 3
mid2 = right - length // 3
if self.getValue(nums, mid1) < self.getValue(nums, mid2):
right = mid2
else:
left = mid1
# 暴力查找最后几个点
min_value = float('inf')
ans = left
for i in range(left, right):
value = self.getValue(nums, i)
if value < min_value:
min_value = value
ans = i
return ans
实数三分
算法思想
- 确定答案的取值范围[left, right)
- 设定枚举次数(通常100次足够)
- 取两个三分点比较函数值
- 每次排除三分之一的区间
代码实现
class Solution {
public:
double getValue(vector<double>& points, double x) {
// 计算在位置x处的函数值
double maxDist = 0;
for (double point : points) {
maxDist = max(maxDist, abs(point - x));
}
return maxDist;
}
double findMin(vector<double>& points) {
double left = *min_element(points.begin(), points.end());
double right = *max_element(points.begin(), points.end());
// 三分100次,相对误差约为(2/3)^100
for (int i = 0; i < 100; i++) {
double len = right - left;
double mid1 = left + len / 3;
double mid2 = right - len / 3;
if (getValue(points, mid1) < getValue(points, mid2)) {
right = mid2;
} else {
left = mid1;
}
}
return left;
}
};
时间复杂度分析
整数三分 | ||
实数三分 |
其中 是计算函数值的时间复杂度,
是三分次数(通常取100)。
应用场景
- 单峰函数极值
- 单谷函数极值
- 凸/凹函数最值
- 距离最值问题
- 最优分割点查找
注意事项
- 函数的单调性判断
- 三分点的选择
- 精度要求的控制
- 整数与实数的区分
- 边界情况的处理
常见变形
- 查找最大值
int findMax(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (right - left >= 3) {
int len = right - left;
int mid1 = left + len / 3;
int mid2 = right - len / 3;
if (nums[mid1] > nums[mid2]) {
right = mid2;
} else {
left = mid1;
}
}
int maxVal = nums[left];
for (int i = left + 1; i <= right; i++) {
maxVal = max(maxVal, nums[i]);
}
return maxVal;
}
class Solution {
public int findMax(int[] nums) {
int left = 0, right = nums.length - 1;
while (right - left >= 3) {
int len = right - left;
int mid1 = left + len / 3;
int mid2 = right - len / 3;
if (nums[mid1] > nums[mid2]) {
right = mid2;
} else {
left = mid1;
}
}
int maxVal = nums[left];
for (int i = left + 1; i <= right; i++) {
maxVal = Math.max(maxVal, nums[i]);
}
return maxVal;
}
}
class Solution:
def findMax(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while right - left >= 3:
length = right - left
mid1 = left + length // 3
mid2 = right - length // 3
if nums[mid1] > nums[mid2]:
right = mid2
else:
left = mid1
return max(nums[i] for i in range(left, right + 1))
- 查找最小值
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (right - left >= 3) {
int len = right - left;
int mid1 = left + len / 3;
int mid2 = right - len / 3;
if (nums[mid1] < nums[mid2]) {
right = mid2;
} else {
left = mid1;
}
}
int minVal = nums[left];
for (int i = left + 1; i <= right; i++) {
minVal = min(minVal, nums[i]);
}
return minVal;
}
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (right - left >= 3) {
int len = right - left;
int mid1 = left + len / 3;
int mid2 = right - len / 3;
if (nums[mid1] < nums[mid2]) {
right = mid2;
} else {
left = mid1;
}
}
int minVal = nums[left];
for (int i = left + 1; i <= right; i++) {
minVal = Math.min(minVal, nums[i]);
}
return minVal;
}
}
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while right - left >= 3:
length = right - left
mid1 = left + length // 3
mid2 = right - length // 3
if nums[mid1] < nums[mid2]:
right = mid2
else:
left = mid1
return min(nums[i] for i in range(left, right + 1))
经典例题
牛客代码笔记-牛栋 文章被收录于专栏
汗牛充栋,学海无涯。<br/> 内含算法知识点讲解,以及牛客题库精选例题。<br/> 学习算法,从牛栋开始。