Python：每日一题 225

506297018

每日一道题

506297018

每日一道题

新手·ing

fan1993423 发表于 2019-7-23 15:32
嗯，全栈先等会吧，我现在学的方向是机器学习，深度学习，神经网络，能把这些搞明白我就很满足了，高等数 ...

大佬求带

fan1993423

新手·ing 发表于 2019-7-23 15:49
大佬求带

我还有很多地方不太懂，导师要求写小论文，所以任重而道远，大佬真的就如塔利班，冬雪雪冬，他们真的厉害，我有些代码也都是向他们学习的。

archlzy

def fun(test_list):
    result = []
    for i in range(len(test_list)):
        m = None
        j = 1
        while m == None and i+j < len(test_list):
            if test_list[i] < test_list[i+j]:
                m = j
            j += 1
        if m == None:
            m = 0
            j += 1
        result.append(m)
    return result

776667

def fun225(x):
    result = []
    for i in range(len(x)):
        for j in range(i+1,len(x)):
            if x[j] > x[i]:
                result.append(j-i)
                break
        else:
            result.append(0)
    return result

if __name__ == '__main__':
    print(fun225([73, 74, 75, 71, 69, 72, 76, 73]))

[1, 1, 4, 2, 1, 1, 0, 0]
>>> 

四维理工男

感谢

jerryxjr1220

提供下思路，从后往前循环，只要循环一遍就能出结果了，复杂度N
你从前往后循环的复杂度至少是N*N/2

新手·ing

jerryxjr1220 发表于 2019-7-26 15:36
提供下思路，从后往前循环，只要循环一遍就能出结果了，复杂度N
你从前往后循环的复杂度至少是N*N/2

大佬，收到

a850698824

111

fan1993423

jerryxjr1220 发表于 2019-7-26 15:36
提供下思路，从后往前循环，只要循环一遍就能出结果了，复杂度N
你从前往后循环的复杂度至少是N*N/2

来，来，科普一下复杂度

fan1993423

jerryxjr1220 发表于 2019-7-26 15:36
提供下思路，从后往前循环，只要循环一遍就能出结果了，复杂度N
你从前往后循环的复杂度至少是N*N/2

就比如说我做的那个思路复杂度是多少，怎么判断或者说这个标准是什么，好多题会做但是也许将题复杂化了

永恒的蓝色梦想

def func(x):
  lis=[]
  n=len(x)
  for i in range(n):
    for j in range(i+1,n):
      if x[j]>x[i]:
        lis.append(j-i)
        break
    else:lis.append(0)
  return lis

改进：

def func(x):
  m=max(x)
  lis=[]
  n=len(x)
  for i in range(n):
    if i==m:
          lis.append(0)
          continue
    for j in range(i+1,n):
      if x[j]>x[i]:
        lis.append(j-i)
        break
  return lis

踏歌行天路

import random as r

a = []
b = []
for i in range(10):
    a.append(r.randint(30,100))
for j in range(10):
    for k in range(j,10):
        if a[j] < a[k]:
            b.append(k-j)
            break
    else:
         b.append(0)
print(a)
print(b)

wlchcarl

def dailyTemperatures(temps):
    temp = []
    res = [0]*len(temps)    
    for index, temperature in enumerate(temps):
        if len(temp) == 0:
            temp.append([index,temperature])
        else:
            while len(temp) > 0:
                tail = temp.pop()
                if tail[1] < temperature:
                    res[tail[0]] = index - tail[0]
                else:
                    temp.append(tail)
                    break
            temp.append([index,temperature])
    return(res)

楼主帮我看看这个行不行，别看有两重循环，复杂度应该是O(n)的

wlchcarl

fan1993423 发表于 2019-7-27 20:40
就比如说我做的那个思路复杂度是多少，怎么判断或者说这个标准是什么，好多题会做但是也许将题复杂化了

你这个复杂度O(n^2)了，楼主那个testcase循环了25462474次。复杂度的概念涉及到极限，无穷大什么的，一时半会讲不清楚。

我们考虑复杂度时一般考虑的都是最坏情况，这道题里所有

“依次对每一个温度都往后找最近的比这个温度高的温度”  这种方案

的最坏的情况是所有温度是一个单调递减的数列，也就是说对每一个温度而言都要遍历这个温度后面的所有温度才知道没有比它更高的温度了，假设有n个温度的话就要循环

(n-1)+(n-2)+(n-3)+...+2+1 = n*(n-1)/2 次

假设每一次循环都要执行C次操作（比如append，pop等）
那么总共就要执行C*n*(n-1)/2 个操作
当n变得很大时，这个式子中的一次项-C*n/2的影响就会变得很小，二次项C*n^2/2占据了主导地位。

这是一个二次函数，你可以认为所有二次函数的复杂度都可以写为O(n^2),在n变得很大时，二次函数的增长要比一次函数（这里可以认为所有一次函数的复杂度都可以写为O(n)）快得多，也就是说随着n变得很大，二次函数个操作执行起来要比一次函数个操作要慢得多。这时候如果有人设计出一个复杂度为O(n)，也就是只需要执行一次函数个操作的程序，运行时间将会大大缩短。

比方说楼主给的那个一万个温度的testcase，O(n)复杂度只需要执行几万次，十几万次操作，而O(n^2)复杂度就可能要执行上亿次操作了。时间差距就很明显了。

啊我不是很会讲题，语言可能组织的不是很好，望谅解~

fan1993423

wlchcarl 发表于 2019-7-28 14:28
你这个复杂度O(n^2)了，楼主那个testcase循环了25462474次。复杂度的概念涉及到极限，无穷大什么的，一时 ...

我只用了一个循环都是N^2的复杂度？

fan1993423

wlchcarl 发表于 2019-7-28 14:28
你这个复杂度O(n^2)了，楼主那个testcase循环了25462474次。复杂度的概念涉及到极限，无穷大什么的，一时 ...

那你这个复杂度是多少？

老歪是也

一下没看懂题

wlchcarl

fan1993423 发表于 2019-7-28 19:27
那你这个复杂度是多少？

我的思路是创建一个临时的栈，挨个遍历所有温度，栈空就把温度和它的索引存进去。后来的温度会和栈顶的温度进行比较，如果栈顶的温度高，那么后来的温度入栈。这保证了栈里的温度是由高到低排列的，后来的温度只需要不断地与栈顶那个栈里最低的温度比较。如果后来的温度比栈顶的温度都低，那么就不用继续比下去。如果栈顶的温度低，后来的温度高，满足题目条件，根据索引计算结果写入答案，并把栈顶的温度弹（pop）出来，然后继续此过程，直到后来的温度比栈里任何温度都低或者栈空为止，最后后来的温度入栈。

我的代码里每次比较都把栈顶温度pop了出来，事实上只是写起来方便，并不必要。按照以上思路，所有温度都入栈一次，总共执行n次，所有温度都至多出栈一次，总共执行至多n次。总共的循环次数和比较次数也不过是n的常数倍，整体时间复杂度为O(n)。事实上，在楼主的那个一万个温度的testcase里，我的代码循环了一万多次。

这样的思路时间复杂度O(n),空间复杂度O(n)，牺牲了一定的空间去存储温度和它的索引，以便于换取速度上的优势。对这题而言，O(n)的时间复杂度应该是极限了，但也许有更好的θ(1)的空间复杂度的算法，只牺牲常数级的空间，期待大神解答了。

自己没写过几个程序，可能我的代码显得稚嫩，望指点。