首先这个题我们看一下数据量,是1e9的数据量(意思就是n最大为1e9),假如按照题意我们暴力做法就是每个数字从大到小枚举肯定会超时的,那怎么做呢,那我们首先要想到根据奇偶找规律,我们会发现奇数就是自己本身,那偶数的规律是什么呢,对于一个偶数x,我们只需要每次除以2直到这个数变成奇数那这个奇数就是我们要求的答案,因为2是一个属偶数的最小因数(除了1),所以每次除以2得到的奇数就是我们要找的答案,其实不少人都想到了这一步但是还是超时,那我们来看一下这种做法的时间复杂度对于奇数肯定是O(N),就算你提前那等差数列求那就算O(1),那偶数我们每次除以2时间复杂度就是O(NlogN),我们数据量为1e9,所以还是会超时。 那正确做法就是,刚刚也说到了对于奇数我们可以直接等差数列求和实现O(1)处理,偶数每次除以2,接下来我举个例子你们体会一下,比如1 2 3 4 5 6 7 8 9 10,奇数我们直接求和,偶数除以2,那奇数就没了偶数就变成了1 2 3 4 5,然后我们又回到上一步继续对奇数求和偶数除以2,就变成了1 2,继续对奇数求和偶数除以2,就变成了1,对奇数求和偶数除以2,然后就结束了就算出来了正确答案,我们发现没必要对单个数字进行处理,而是对N进行直接处理,这么处理下来就是O(logN)的复杂度

0 条评论

目前还没有评论...