时间戳

首页 > 解决方案 > 将链表中的元素与列表的其余部分进行比较python

python - 将链表中的元素与列表的其余部分进行比较python

问题描述

所以我在处理当前的问题时遇到了麻烦。该问题提示我们获取一个链表并将每个元素与列表的其余部分进行比较，并返回重复项的总数。例如列表是 [1,2,3,1,4,2,] 这应该返回 2 个重复项 1 和 2。我尝试使用列表的长度循环遍历列表，但仍然得到错误的输出。我在下面提供了我的尝试，提前感谢您的帮助。

def solution1 (llist):
  counter = 0
  length=0
  curr = llist.head

  while curr:
   length+=1
   curr=curr.next

  while curr:
    for _ in range(length):
      if curr.item == curr.next.item:
        counter+=1
    curr = curr.next
 

  return counter

预期产出——

llist= 1-->2-->3-->1-->4-->2

output:2

标签： pythonlinked-list

解决方案

你快到了。下面是使用嵌套循环的蛮力方法。维持两个柜台first和second。每当它们的值匹配时，就意味着它是重复的。增加计数器并继续。

时间复杂度：O(n^2)

def solution1(llist):
    counter = 0
    first = llist.head
    
    while first:
        second = first.next
        while second:
            if first.item == second.item: # duplicate
                counter += 1
                break
            second = second.next
        first = first.next      
    return counter

一种更优化的方法是在迭代时保持元素计数。返回 count > 1 的键。

时间复杂度：O(n)

import collections
def solution1(llist):
    curr = llist.head
    counts = collections.defaultdict(int)
    while curr:
        counts[curr.item] += 1
        curr = curr.next
    print(counts)
    return sum(1 for i in counts if counts[i] > 1)

推荐阅读