获取热门电影算法

功能#2：获取热门电影

为我们的“Netflix”项目实现“获取热门电影”功能。

我们将介绍以下内容

描述

解决方案
复杂性措施
时间复杂度
空间复杂度
描述#
现在，我们需要建立一个标准，以便将来自多个国家的顶级电影组合成一个单一的顶级电影列表。为了扩展，内容搜索以分布式方式执行。每个国家/地区的搜索结果在单独的列表中生成。给定列表的每个成员都按受欢迎程度排名，1最受欢迎和受欢迎程度随着排名数字的增加而下降。

假设以下标题由提供的 ID 表示：
在这里插入图片描述

电影映射到他们的行列
我们将得到n 个列表，这些列表都按受欢迎程度的升序排列。我们必须将这些列表组合成一个列表，该列表将按升序排序，即从最好到最差。

请记住，排名对于个别电影是唯一的，一个排名可以在多个列表中。

让我们通过一个插图更好地理解这一点：
在这里插入图片描述

将多个评级列表合并为一个

解决方案#

由于我们的任务涉及多个列表，因此您应该将问题分解为多个任务，从一次合并两个列表的问题开始。然后，您应该将前两个列表的结果与第三个列表相结合，依此类推，直到达到最后一个。

让我们讨论一下我们将如何实现这个过程：

将第一个列表视为结果，并将其存储在一个变量中。
遍历列表的列表，从第二个列表开始，并将其与我们存储的列表组合为结果。结果应该存储在同一个变量中。
当组合两个列表时，比如l1和l2，维护一个prev指向虚拟节点的指针。
如果 list 的值l1小于或等于 list 的值l2，则将前一个节点连接到l1并递增l1。否则，对 list 执行相同的操作l2。
继续重复上述步骤，直到一个列表指向一个nil值。
将非零列表连接到合并后的列表并返回。

让我们看看下面解决方案的代码：

package mainfunc merge2SortedLists(l1, l2 *LinkedListNode) *LinkedListNode {dummy := &LinkedListNode{data: -1}prev := dummyfor l1 != nil && l2 != nil {if l1.data <= l2.data {prev.next = l1l1 = l1.next} else {prev.next = l2l2 = l2.next}prev = prev.next}if l1 == nil {prev.next = l2} else {prev.next = l1}return dummy.next
}func mergeKSortedLists(lists []*LinkedListNode) *LinkedListNode {if len(lists) > 0 {res := lists[0]for i := 1; i < len(lists); i++ {res = merge2SortedLists(res, lists[i])}return res}return &LinkedListNode{data: -1}
}func main() {a := createLinkedList([]int{11, 41, 51})b := createLinkedList([]int{21,23,42})c := createLinkedList([]int{25,56,66,72})list1 := []*LinkedListNode{a, b, c}display(mergeKSortedLists(list1))
}

package mainimport ("fmt""math/rand"
)type LinkedListNode struct {key              intdata             intnext             *LinkedListNodearbitrartPointer *LinkedListNode
}func createLinkedList(lst []int) *LinkedListNode {var head *LinkedListNodevar tail *LinkedListNodefor _, x := range lst {newNode := &LinkedListNode{data: x}if head == nil {head = newNode} else {tail.next = newNode}tail = newNode}return head
}func insertAtHead(head *LinkedListNode, data int) *LinkedListNode {newNode := &LinkedListNode{data: data}newNode.next = headreturn newNode
}func insertAtTail(head *LinkedListNode, data int) *LinkedListNode {newNode := &LinkedListNode{data: data}if head == nil {return newNode}temp := headfor temp.next != nil {temp = temp.next}temp.next = newNodereturn head
}func createRandomList(length int) *LinkedListNode {var listHead *LinkedListNodefor i := 0; i < length; i++ {listHead = insertAtHead(listHead, rand.Intn(100))}return listHead
}func toList(head *LinkedListNode) []int {var lst []inttemp := headfor temp != nil {lst = append(lst, temp.data)temp = temp.next}return lst
}func display(head *LinkedListNode) {temp := headfor temp != nil {fmt.Printf("%d", temp.data)temp = temp.nextif temp != nil {fmt.Printf(", ")}}fmt.Printf("\n")
}func mergeAlternating(list1, list2 *LinkedListNode) *LinkedListNode {if list1 == nil {return list2}if list2 == nil {return list1}head := list1for list1.next != nil && list2 != nil {temp := list2list2 = list2.nexttemp.next = list1.nextlist1.next = templist1 = temp.next}if list1.next == nil {list1.next = list2}return head
}func isEqual(list1, list2 *LinkedListNode) bool {if list1 == list2 {return true}for list1 != nil && list2 != nil {if list1.data != list2.data {return false}list1 = list1.nextlist2 = list2.next}return (list1 == list2)
}