三分答案

三分答案

问题描述

三分答案是一种用于查找单峰/单谷函数极值的搜索算法。通过将区间分成三份,比较两个三分点的函数值来确定极值的位置。

整数三分

算法思想

  1. 确定答案的取值范围[left, right)
  2. 取两个三分点 mid1 和 mid2
  3. 比较两点函数值确定搜索方向
  4. 每次排除三分之一的区间

代码实现

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

实数三分

算法思想

  1. 确定答案的取值范围[left, right)
  2. 设定枚举次数(通常100次足够)
  3. 取两个三分点比较函数值
  4. 每次排除三分之一的区间

代码实现

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)。

应用场景

  1. 单峰函数极值
  2. 单谷函数极值
  3. 凸/凹函数最值
  4. 距离最值问题
  5. 最优分割点查找

注意事项

  1. 函数的单调性判断
  2. 三分点的选择
  3. 精度要求的控制
  4. 整数与实数的区分
  5. 边界情况的处理

常见变形

  1. 查找最大值
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))
  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))

经典例题

  1. 【模板】整数域三分
  2. 游游开车出游
  3. 游游的数值距离
牛客代码笔记-牛栋 文章被收录于专栏

汗牛充栋,学海无涯。<br/> 内含算法知识点讲解,以及牛客题库精选例题。<br/> 学习算法,从牛栋开始。

全部评论

相关推荐

嘀哩咕噜说啥呢:27届,这简历,强的逆天,大厂实习随便冲,面经多少看点,hot100刷完,大厂随便挑了
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务