侧边栏壁纸
  • 累计撰写 4 篇文章
  • 累计创建 17 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

寻找小于k的最大数

Harry Yang
2024-09-13 / 0 评论 / 0 点赞 / 16 阅读 / 4940 字 / 正在检测是否收录...

问题描述

数组 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。

......

思路

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

小于k的最大数1.png

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

如果无法匹配到任何数字,则说明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
}

0

评论区