求将整数钳位至指定范围并替换为指定尾数的高效算法

我们需要实现一个算法，完成以下核心操作：

1. 将输入整数value限制在min和max指定的区间内
2. 将结果的十进制尾数替换为给定已排序列表ends中的某一值，最终结果要尽可能接近原value

核心逻辑分析 #

根据示例可明确规则：

• ends中每个元素的十进制位数，决定了要替换的尾数长度（比如26是2位，就替换结果的最后2位；201是3位，替换最后3位）
• 先基于原value的量级计算基础候选值，再将其调整到[min, max]区间内
• 从所有有效候选中，选择与原value差值绝对值最小的结果；若差值相同，优先选择较大的候选

算法步骤 #

1. 计算尾数量级：对ends中的每个元素，计算其十进制位数d，对应的量级scale = 10^d
2. 生成基础候选：用value除以scale取整得到targetBase，基础候选为targetBase * scale + end
3. 调整候选到区间：
   • 若基础候选小于min，计算大于等于min的最小候选（ceil(min/scale)*scale + end），若超过max则跳过该候选
   • 若基础候选大于max，计算小于等于max的最大候选（floor(max/scale)*scale + end），若小于min则跳过该候选
4. 筛选最优候选：遍历所有有效候选，选择与value差值最小的那个；差值相同时选较大值

伪代码实现 #

function clampAndReplace(value, min, max, ends):
    if min > max:
        raise error("min must be <= max")
    if ends is empty:
        raise error("ends list cannot be empty")
    
    bestCandidate = null
    minDiff = infinity
    
    for each end in ends:
        d = number of decimal digits of end
        scale = 10^d
        
        targetBase = value // scale
        candidate = targetBase * scale + end
        
        if candidate < min:
            requiredBase = ceil(min / scale)
            candidate = requiredBase * scale + end
            if candidate > max:
                continue
        elif candidate > max:
            requiredBase = floor(max / scale)
            candidate = requiredBase * scale + end
            if candidate < min:
                continue
        
        currentDiff = absolute value of (candidate - value)
        if bestCandidate is null or currentDiff < minDiff or (currentDiff == minDiff and candidate > bestCandidate):
            bestCandidate = candidate
            minDiff = currentDiff
    
    if bestCandidate is null:
        raise error("no valid candidate found in the range")
    
    return bestCandidate

Go语言实现 #

package main

import (
	"errors"
	"fmt"
	"math"
)

// ClampAndReplace 将value钳位在[min, max]范围内，替换尾数为ends中的值，返回最接近原value的结果
func ClampAndReplace(value, min, max int, ends []int) (int, error) {
	if min > max {
		return 0, errors.New("min must be less than or equal to max")
	}
	if len(ends) == 0 {
		return 0, errors.New("ends list cannot be empty")
	}

	bestCandidate := 0
	minDiff := math.MaxInt

	for _, end := range ends {
		if end < 0 {
			continue
		}
		// 计算end的十进制位数，得到对应的量级scale
		d := numDigits(end)
		scale := int(math.Pow10(d))

		targetBase := value / scale
		candidate := targetBase*scale + end

		// 将候选值调整到[min, max]区间内
		switch {
		case candidate < min:
			// 正整数下，(min + scale -1)/scale等价于ceil(min/scale)
			requiredBase := (min + scale - 1) / scale
			candidate = requiredBase*scale + end
			if candidate > max {
				continue
			}
		case candidate > max:
			// 正整数下，max/scale直接是floor结果
			requiredBase := max / scale
			candidate = requiredBase*scale + end
			if candidate < min {
				continue
			}
		}

		// 计算当前候选与原value的差值绝对值
		diff := abs(candidate - value)
		// 更新最优候选：优先选差值小的，差值相同选较大的候选
		if minDiff == math.MaxInt || diff < minDiff || (diff == minDiff && candidate > bestCandidate) {
			bestCandidate = candidate
			minDiff = diff
		}
	}

	if minDiff == math.MaxInt {
		return 0, errors.New("no valid candidate found in [min, max] range")
	}

	return bestCandidate, nil
}

// numDigits 计算正整数的十进制位数
func numDigits(n int) int {
	if n == 0 {
		return 1
	}
	count := 0
	for n > 0 {
		count++
		n /= 10
	}
	return count
}

// abs 返回整数的绝对值
func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

func main() {
	// 示例测试参数
	ends := []int{26, 201, 330}
	min := 5350
	max := 7392

	tests := []struct {
		value    int
		expected int
	}{
		{2000, 5426},
		{6205, 6201},
		{7400, 7330},
	}

	for _, test := range tests {
		result, err := ClampAndReplace(test.value, min, max, ends)
		if err != nil {
			fmt.Printf("Value %d: error - %v\n", test.value, err)
			continue
		}
		fmt.Printf("Value: %d -> %d (expected: %d)\n", test.value, result, test.expected)
	}
}

测试结果 #

运行上述Go代码，输出与示例完全一致：

Value: 2000 -> 5426 (expected: 5426)
Value: 6205 -> 6201 (expected: 6201)
Value: 7400 -> 7330 (expected: 7330)

内容的提问来源于stack exchange，提问作者Raven