leecode | python刷题实战的一些问题与解决笔记

解2（最优解）：用字典的方式。

执行用时24ms，内存消耗16.1MB。

#定义一个空字典。

命名随便。

这里命名为hashmap，因为python里的字典相当于java里的hashmap。


    hashmap = {}
    for index,num in enumerate(nums):
        another_num = target - num
        #如果另一个数字在字典中，则执行以下返回语句
        if another_num in hashmap:
            return [hashmap[another_num],index]
        #存入字典：字典[key] = value
        hashmap[num] = index

题目要求：

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。

元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。

更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

（这一句还不太懂）
来源：力扣（LeetCode）——链接

解1：执行用时3032ms，内存消耗16.9MB

class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
    #统计数组元素的索引值（元素值相同时，索引值也相同）
    index_list = []
    for i in nums:
        index_list.append(nums.index(i))
    
    #从后往前遍历，当索引列表中：后一个元素值与前一个元素值相同时，取出后一个元素的索引值，删除原数组中对应位置上的索引
    length = len(nums)
    i = length-1
    while i>0:
        if index_list[i] == index_list[i-1]:
            nums.pop(i)
            i -= 1
        else:
            i -= 1
    return len(nums)

解2：执行用时40ms，内存消耗16MB

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
    	#把解1中的第一部分换成这一句
		nums.sort()

        #从后往前遍历，当索引列表中：后一个元素值与前一个元素值相同时，取出后一个元素的索引值，删除原数组中对应位置上的索引
        length = len(nums)
        i = length-1
        while i>0:
            if nums[i] == nums[i-1]:
                nums.pop(i)
                i -= 1
            else:
                i -= 1
        return len(nums)

题目要求：不使用额外空间
思路：往位运算上想
知识点：

交换律：a ^ b ^ c <=> a ^ c ^ b
任何数于0异或为任何数 0 ^ n => n
相同的数异或为0: n ^ n => 0

var a = [2,3,2,4,4]
2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3

关键代码：

a = 0
for i in nums:
	a = a ^ i
return a

要求：找出数组中出现次数大于n/2的数字
方法：摩尔投票法 时间复杂度O(N) 空间复杂度O(1)

class Solution {
public:
    int majorityElement(vector& nums) {
//摩尔投票法,先假设第一个数过半数并设cnt=1；遍历后面的数如果相同则cnt+1，不同则减一，当cnt为0时则更换新的数字为候选数（成立前提：有出现次数大于n/2的数存在）
        int res=0,cnt=0;
        for(int i=0;i

class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
    #如果数组中没有重复元素，则返回false
    if len(nums) == len(set(nums)):
        return False

    #反之：有重复元素的情况（将数组表示成字典，将索引值和元素值分开）：
    hashmap = {}
    j = -1
    for index,num in enumerate(nums):
        #给字典中存入第一组数
        if len(hashmap) < 1:
            #存入字典：字典[key] = value
            hashmap[num] = index

        #和前面已经存入hashmap的比较：
        else:
            #如果出现了重复元素，检查索引值的间距是否符合要求
            if num in hashmap:
                j += 1
                if len(hashmap)+j - hashmap[num] <= k:
                    return True
                else:
                    #如果不符合，删除旧数据，存入新数据
                    del hashmap[num]
                    hashmap[num] = index                     
            else:
                hashmap[num] = index

    return False

class Solution:
def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:

    #将数组表示成字典，将索引值和元素值分开：
    hashmap = {}
    for index,num in enumerate(nums):
        #如果出现了重复元素，检查索引值的间距是否符合要求
        if (num in hashmap) and (index - hashmap[num] <= k):
                return True
        hashmap[num] = index                     

    return False