设为首页 加入收藏

TOP

数据流中的第k大元素的golang实现
2018-12-12 16:11:36 】 浏览:47
Tags:数据流 元素 golang 实现

设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第K大的元素。

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

这道题我们可以想到使用优先队列来做,优先队列的长度为K,按照从小到大排序,那么取出第K大的就是取出下标为0的值

首先我们构造一个小顶堆的数据结构

type KthLargest struct {
    PriorityQueue []int //优先队列
    Size          int   //小顶堆的容量
}
func Constructor(k int, nums []int) KthLargest {
    var ks KthLargest
    ks.Size = k
    for index := 0; index < len(nums); index++ {
        ks.Add(nums[index])
    }
    return ks
}

func (this *KthLargest) Add(val int) int {
    if len(this.PriorityQueue) < this.Size {
        this.PriorityQueue = append(this.PriorityQueue, val)
    } else if this.PriorityQueue[0] <= val {
        this.PriorityQueue = this.PriorityQueue[1:]
        this.PriorityQueue = append(this.PriorityQueue, val)
    }
    sort.Ints(this.PriorityQueue)
    return this.PriorityQueue[0]
}

这里是一个耗时的做法,因为这里每次添加元素的时候,我们都会去排序,把堆内元素最小的放在最前

而我们可以通过实现golang中的堆的几个接口来自定义我们的堆类型

type intHeap []int

//下面几个方法是实现head的接口
func (h intHeap) Len() int {
    return len(h)
}

func (h intHeap) Less(i, j int) bool {
    return h[i] < h[j]
}

func (h intHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h *intHeap) Push(x interface{}) {
    // Push 使用 *h,是因为
    // Push 增加了 h 的长度
    *h = append(*h, x.(int))
}

func (h *intHeap) Pop() interface{} {
    // Pop 使用 *h ,是因为
    // Pop 减短了 h 的长度
    res := (*h)[len(*h)-1]
    *h = (*h)[:len(*h)-1]
    return res
}

实现了之后,我们就可以非常简单和快捷的操作堆了

type KthLargest struct {
    k    int
    heap intHeap
}

// Constructor 创建 KthLargest
func Constructor(k int, nums []int) KthLargest {
    h := intHeap(nums)
    heap.Init(&h)

    for len(h) > k {
        heap.Pop(&h)
    }

    return KthLargest{
        k:    k,
        heap: h,
    }
}

// Add 负责添加元素
func (kl *KthLargest) Add(val int) int {
    heap.Push(&kl.heap, val)

    if len(kl.heap) > kl.k {
        heap.Pop(&kl.heap)
    }

    return kl.heap[0]
}

 


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇浏览器与go语言的websocket通信 下一篇环形链表得golang实现

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }