寻找小于k的最大数

问题描述

数组 Arr 中给定可以使用的 1~9 的数，返回由数组 Arr 中的元素组成的小于 n 的最大数。

示例 1：Arr={1, 2, 9, 4}，n=2533，返回 2499。

示例 2：Arr={1, 2, 5, 4}，n=2543，返回 2542。

示例 3：Arr={1, 2, 5, 4}，n=2541，返回 2525。

示例 4：Arr={1, 2, 9, 4}，n=2111，返回 1999。

示例 5：Arr={5, 9}，n=5555，返回 999。

......

思路

一个小于某个数的最大数的常见形式是前几位数字和目标数字一样，从某一位开始比目标数对应的位置要小（极限情况是从第一位开始就比目标数字小），那么可以尝试先从左向右进行匹配，当匹配不到时，就取一个小于目标位数字的数填充，剩余位置用数组中的最大数字填充，就是答案。类似下面这样：

当匹配完成，下一位无法寻找到比目标数字更小的数字时，需要向后回退一步，在上一位寻找小于目标数字的最大数字，后面依然使用最大数字填充：

如果无法匹配到任何数字，则说明Arr集合中的每个数字都大于目标数中的所有数字，则只能减小答案的位数，选择一个小于目标数长度的最大数：

最后考虑一下集合中只有一个数字的情况，且该数字比目标数大时，是无法找到答案的，返回-1。

代码

package main

import (
	"fmt"
	"strconv"
)

func main() {
	case1 := []int{
		1, 2, 9, 4,
	}
	n1 := 2533
	case2 := []int{
		1, 2, 5, 4,
	}
	n2 := 2543
	case3 := []int{
		1, 2, 5, 4,
	}
	n3 := 2541
	case4 := []int{
		1, 2, 9, 4,
	}
	n4 := 2111
	case5 := []int{
		5, 9,
	}
	n5 := 5555
	case6 := []int{
		1,
	}
	n6 := 2
	case7 := []int{
		3,
	}
	n7 := 2

	fmt.Println(solution(case1, n1) == 2499)
	fmt.Println(solution(case2, n2) == 2542)
	fmt.Println(solution(case3, n3) == 2525)
	fmt.Println(solution(case4, n4) == 1999)
	fmt.Println(solution(case5, n5) == 999)
	fmt.Println(solution(case6, n6) == 1)
	fmt.Println(solution(case7, n7) == -1)
}

func solution(arr []int, k int) int {
	maxN := findMaxNum(arr) //记录数组中最大的数，后面会用
	m := map[int]bool{}     // 使用map便于查找某个数字是否存在
	for _, n := range arr {
		m[n] = true
	}

	result := ""
	kStr := strconv.Itoa(k)

	// 先尝试从左往右去匹配目标值，只匹配到倒数第二位，防止完全匹配到目标值（因为答案要小于目标值）
	for i := 0; i < len(kStr)-1; i++ {
		b := kStr[i] - '0'
		if m[int(b)] {
			result += strconv.Itoa(int(b))
		} else {
			break
		}
	}

	// 再尝试补充后面的数字
	// 首先找到小于k的最大数字填充一位，剩余位使用maxN填充
	a := findMaxNumLessThanK(arr, int(kStr[len(result)]-'0'))
	if a != -1 {
		result += strconv.Itoa(a)
		for i := len(result); i < len(kStr); i++ {
			result += strconv.Itoa(maxN)
		}
		r, _ := strconv.Atoi(result)
		return r
	} else {
		// 如果没有找到小于k的数字，需要向后退一位，重新寻找小于当前位的最大数，剩余数字还是用maxN填充
		for len(result) > 0 {
			result = result[:len(result)-1]
			b := findMaxNumLessThanK(arr, int(kStr[len(result)]-'0'))
			if b != -1 {
				result += strconv.Itoa(b)
				for i := len(result); i < len(kStr); i++ {
					result += strconv.Itoa(maxN)
				}
				r, _ := strconv.Atoi(result)
				return r
			}
		}

		// 此时意味着通过匹配的方式无法找到答案，减小位数寻找一个最大值即可
		for i := 0; i < len(kStr)-1; i++ {
			result += strconv.Itoa(maxN)
		}

		// 此时意味着arr中的所有数字都比k大，应该返回-1
		if len(result) <= 0 {
			return -1
		}
		r, _ := strconv.Atoi(result)
		return r
	}
}

// 寻找数组中小于k的最大数字，k需要保证是一位
func findMaxNumLessThanK(arr []int, k int) int {
	result := -1
	for _, n := range arr {
		if n < k && result < n {
			result = n
		}
	}
	return result
}

// 寻找数组中的最大数字
func findMaxNum(arr []int) int {
	result := arr[0]
	for _, n := range arr {
		if n > result {
			result = n
		}
	}
	return result
}