阿里算法工程师2018笔试题——菜鸟货架编号，O(n)解法
题目描述：
题目简述:
仓库编号为0-9整数
以下为一示例：
1|12|123|1234|12345|……|12345678910111213141516|…
每一个整数代表一个格子，现给出一格子位置（从左到右第几个）求其编号
仓库编号为0-9整数
以下为一示例：
1|12|123|1234|12345|……|12345678910111213141516|…
每一个整数代表一个格子，现给出一格子位置（从左到右第几个）求其编号
数据范围：1 ≤ k≤ 10^9
思路：
观察到：
第c行有c个数字
把从1到c累加起来，就有c*（c+1）/2个。
假设：
第k个号码在第c+1行，第p个
那么就有关于p的恒等关系：
k-p=c*（c+1）/2
求p的解法就是：
那么把c从1到k遍历，就可以获得p
比较p跟c+1的大小：如果p>c+1，那么也就是这一行里没有这么大的一个index，那么就舍弃，直到p<=c+1
知道了p是多少，就知道了第k个是这一行里第p个
因为这个编号都是p mod 10那么就p mod 10得答案
复杂度：
遍历一次，所以O(n)
代码：
k=int(input())
for c in range(1,k):
p=int(k-((c+1)*c)/2)
if p<=(c+1):
print (p%10)
break #阿里巴巴##算法工程师#
查看6道真题和解析