IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 算法练习-leetcode-1.两数之和 -> 正文阅读

[数据结构与算法]算法练习-leetcode-1.两数之和

题目

leetcode-1.两数之和

我的

解题思路:

  • 排序后,折半查找
  • 时间复杂度: O(nlogn) (其实取决于排序算法的时间复杂度,这里默认快排,最小的时间复杂度)
  • 空间复杂度:O(n)

解题代码:

class Solution:
    def __init__(self):
        self.resl = 0
        self.resr = 0

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        numsTemp = sorted(nums) # 快排 时间复杂度O(nlogn)
        print(nums)

        self.twoSumLoop(numsTemp,target,0,len(nums)-1) # 递归twoSumLoop 时间复杂度O(n)
        resl = nums.index(numsTemp[self.resl]) # 求指定元素的第一个下标 时间复杂度O(n)
        resr = nums.index(numsTemp[self.resr]) # 求指定元素的第一个下标 时间复杂度O(n)
        if resl == resr:
            for index in range(0,len(nums)): # 求指定元素的第二个下标 时间复杂度O(n)
                if nums[index] == nums[resl] and index != resl:
                    resr = index
                    break

        return [resl,resr] # 综上 时间复杂度O(nlogn)
        

    def twoSumLoop(self, nums: List[int], target: int, l: int, r: int) -> List[int]: # 递归函数

        if (nums[l]+nums[r]) == target:
            print('test0')
            print('[',l,',',r,']')
            self.resl = l
            self.resr = r
            return
        elif nums[l]+nums[r]>target:
            # max+min > t
            # 缩小max
            print('test1')
            r -= 1
            print(r)
            self.twoSumLoop(nums,target,l,r)
        elif nums[l]+nums[r]<target:
            # max+min < t
            # 放大min
            print('test2')
            l += 1
            self.twoSumLoop(nums,target,l,r)

更好的

解题思路:

  • 哈希表映射
  • 时间复杂度:O(n)(只需要遍历一次数组)
  • 空间复杂度:O(n)

解题代码:

def twoSum(nums, target):
    hashmap={}
    for ind,num in enumerate(nums): # 建立Hash表
	    """ enumerate() 函数用于将一个可遍历的数据对象
	    (如列表、元组或字符串)组合为一个索引序列,
	    同时列出数据和数据下标,一般用在 for 循环当中。"""
        hashmap[num] = ind
    for i,num in enumerate(nums):
        j = hashmap.get(target - num)
        if j is not None and i!=j:
            return [i,j]

"""
	作者:lao-la-rou-yue-jiao-yue-xiang
	链接:https://leetcode-cn.com/problems/two-sum/solution/xiao-bai-pythonji-chong-jie-fa-by-lao-la-rou-yue-j/
	来源:力扣(LeetCode)
	著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
"""
  • Python解法不能直接用 dict,因为dict会去重
  • Hash可以解决重复 key的原因

Hash为什么不怕重复。看评论里有很多人提出这个问题,说hash冲突。 我在这里解答一下这个问题。
1.每次写入时,判断条件不是当前的key本身存不存在,而是key和 tag 之间的差值存不存在,这一点很重要。
2.题目命题说明了一点,假定只有一个解。也就是说重复元素再多都无所谓。 case 1:如果有3个或者以上的重复元素,代表这个重复元素不可能是解,所以写入map的时候直接覆盖也无所谓; case2:如果只有两个重复元素,同样的道理,假如这个重复元素是解,那么必定是两个重复元素的和等于tag。这种情况下,当遇到第二个重复元素时,不会写入map,这个时候直接已经取到解了。
所以这种方式,不用考虑hash冲突的问题。

//语言java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i< nums.length; i++) {
            if(map.containsKey(target - nums[i])) {
                return new int[] {map.get(target-nums[i]),i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

/* 	
	作者:guanpengchn
	链接:https://leetcode-cn.com/problems/two-sum/solution/jie-suan-fa-1-liang-shu-zhi-he-by-guanpengchn/
	来源:力扣(LeetCode)
	著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
*/
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-04-28 12:04:59  更:2022-04-28 12:08:36 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 6:20:12-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码