【python】leetcode 442.数组中重复的数据 字典和元素位置交换

文章目录

• 题目
• 解题思路
• • 1.字典统计（空间不符合）
  • 2.先排序，相同元素在前后 （时间不符合）
  • 3.利用字典 （时间不符合）
  • 4.交换元素位置

---

题目

---

解题思路

1.字典统计（空间不符合）

代码如下：

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        dic={}
        res=[]
        for i in nums:
            dic[i]=dic.get(i,0)+1
        ls=list(dic.items())
        ls.sort(key=lambda x:x[1],reverse=True)
        for j in ls:
            if j[1]==2:
                res.append(j[0])
        return res

2.先排序，相同元素在前后 （时间不符合）

代码如下：

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        nums.sort()
        res=[]
     
        for i in range(len(nums)):
            if i==len(nums)-1:
                return res
            if nums[i]==nums[i+1]:
                res.append(nums[i])  

3.利用字典 （时间不符合）

代码如下：

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:      
        memo={}
        res=[]
        memo[nums[0]]=0
        for i in range(1,len(nums)):
            if nums[i] in memo:
                res.append(nums[i])
            memo[nums[i]]=i   
        return res

4.交换元素位置

代码如下：

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        res=[]
       
        for i in range(len(nums)):
            while nums[i]!=nums[nums[i]-1]:
                temp=nums[i]
                nums[i]=nums[temp-1]
                nums[temp-1]=temp
                  
        for x in range(len(nums)):
            if nums[x]-1!=x:
                res.append(nums[x])
                   
        return res