首页 > 编程语言 > 详细

我的第一道算法题

时间:2018-09-26 21:13:23      阅读:158      评论:0      收藏:0      [点我收藏+]

 

第一次刷leetcode 的算法题.超时了,要换方法.

题目两数之和   注意题目要求 返回[0,1] 这种形式的。

 

暴力法求解两数之和,当数组内的元素过多时,该算法运行超时。

给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。

 

def twoSum( nums, target):
        L = len(nums)
        for i in range(L):
            for j in range(i+1,L):
                a1=nums[i]
                a2=nums[j]
                if a1+a2==target:
                    print([i,j])
nums = [2,7,11,15]
target = 9
twoSum(nums,target)

算法分析: 算法复杂度为 OL-1)) = OL*L

 

 

引申阅读:算法的复杂度https://www.jianshu.com/p/f4cca5ce055a

 Tn= Ofn)  则 fn)是Tn)的上界。

要点:

空间复杂度。

通常来说,只要算法不涉及到动态分配的空间,以及递归、栈所需的空间,空间复杂度通常为0(1)

时间复杂度。

对顺序执行的程序,总的时间复杂度等于其中最大的复杂度。如:

For( i = 0; i < n ; i ++)

{ for ( j=0 ; j <n ; j++)}

 

For( j= 0; j < n ;  j ++)

{jfiowejoi   f}

       此时的复杂度为 maxon^2),o(n)  ) 也即 O(n^2)

 

对于条件判断语句,总的时间复杂度等于其中 时间复杂度最大的  路径 的时间复杂度 .  if {  n }   else { n*n}    则最大复杂度为 On×n)  

 

进阶题目:

Void func (int n) {

   For ( i =2; i<n ; i++)

{  

i*=2;

Printf()

       }

             }

          假设循环次数为t,  则 2^t <n   t=log2)(n)  ,时间复杂度为 Ologn)  默认以2为底。

     

       

 

 

 

方法二:

#思路
#将  target - nums[i]  作为key  ,和下标 i 作为 value存到字典p当中.
#如果在numsi】 里发现和 字典p里的 key  相同的值,则返回字典的 p[nums[i]],

建立了一个新的字典P 哈希算法  时间复杂度 On
class Solution:
    def twoSum(self, nums, target):
        p = { }
        for i in range(len(nums)):
            if nums[i] in p:
                return [p[nums[i]], i]
            else:
                p[target - nums[i]] = i
if __name__ == ‘__main__‘:
    nums = [2,7,11,15]
    target = 9
    so = Solution()
    print(so.twoSum(nums,target))

 

 

我的第一道算法题

原文:https://www.cnblogs.com/zyhe/p/9709655.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!