记一道字节面试题：小于n的最大数

nums = [5,6,8,7]
target = 500
nums.sort()
target = str(target)
def search(nums, target):
    low, high = 0, len(nums) - 1 
    while low < high:
        mid = low + (high - low + 1) // 2
        if nums[mid] <= target:
            low = mid
        else:
            high = mid - 1
    return nums[low] if nums[low] <= target else -1
def getMaxNumbers(nums, target):
    res, ans, flag = [], 0, False
    for i in range(len(target)):
        if flag:
            res.append(nums[-1])
            continue
        subtarget = target[i]
        temp = search(nums, int(subtarget))
        if temp == -1:
            if i == 0:
                if len(target) == 1:
                    return 0
                else:
                    return str(nums[-1]) * (len(target) - 1)
            else:
                index = i - 1
                while temp == -1 and index >= 0:
                    temp = search(nums, int(target[index]) - 1)
                    index -= 1
                if temp == -1:
                    return str(nums[-1]) * (len(target) - 1)
                res[index + 1] = temp
                for j in range(index + 2, i):
                    res[j] = nums[-1]
                res.append(nums[-1])
                flag = True
        else:
            if temp == int(subtarget):
                res.append(temp)
            else:
                res.append(temp)
                flag = True
    for i in range(len(res)):
        ans = ans * 10 + res[i]
    return ans
print(getMaxNumbers(nums, target))

问题描述：给一个数组nums=[5,4,8,2],给一个n=5416，让你从nums中选出一些元素，使得组成的数字是小于n的最大数，比如这个例子应该返回5288，当时没想出来，让面试官换了一道题，事后顺着一些大佬的思路写了下，感觉贪心加二分这个思路比较接近正确答案，有没有人看下这个方法行不行

#字节跳动#

全部评论

推荐最新楼层

西噶

中山大学 Java

void maxNumber(const vector<int> &v, int num) { vector<int> arr, ans; int minChoose=10, maxChoose=0; bool exist[10]; for(int x:v) { exist[x]= true; minChoose = min(minChoose, x); //可选择的最小值 maxChoose = max(maxChoose, x); //可选择的最大值 } while(num) //将num每一位存到数组 { arr.push_back(num%10); num /= 10; } reverse(arr.begin(), arr.end()); //答案应尽可能和num位数相同，若位数相同无解，则答案减少一位且每位取最大值，如100 {2,3,4}的答案为44 for(int i=0;i<arr.size>= minChoose ? arr[i] : arr[i] - 1); while (j >= 0 && !exist[j]) j--; if(j<0) //同位数无解，退而求次降低解的位数 { ans.clear(); for (int k = 0; k < arr.size() - 1; ++k) ans.push_back(maxChoose); break; } else if(j!=arr[i]) //当前位取了小于原数同位的值，则解确定，后面每一位都可以取最大值 { ans.push_back(j); while (ans.size()</arr.size></int></int>

1 回复分享

发布于 2022-05-03 16:16

郑胤初

中华女子学院 iOS开发

实际上数只有十个那我们贪心就好了我们首先匹配这个数如果每一位都在这个数组中存在就修改最小的一位如果不就把最高的不能匹配的位之后变成数组中最大值这一位找一个小的数代替

记一道字节面试题：小于n的最大数

全站热榜

创作者周榜