Leetcode heap correlation

q215 The... In the array k The biggest element

Subject portal

Answer key

Although the title requires that the number in the array be returned k The biggest element , But what I build is a small root pile , Because when building a small root heap , Assigning values to the result array starts from large to small , That is, assign values from the end of the array . So when the last sorting operation is traversed , When len(nums) - i == k when , Go straight back to nums[i] that will do .

func findKthLargest(nums []int, k int) int {
    
	//  Building the heap 
	for i := len(nums) / 2 - 1; i >= 0; i-- {
    
		heapify(nums, len(nums), i)
	}
	for i := len(nums) - 1; i > 0; i-- {
    
		nums[i], nums[0] = nums[0], nums[i]
		heapify(nums, i, 0)
		if len(nums) - i == k {
    
			return nums[i]
		}
	}
	return nums[0]
}

func heapify(arr []int, n int, i int) {
    
	// Heap maintenance 
	largest := i  		//i Is the subscript of the current parent node 
	lson := i * 2 + 1   // Left the child 
	rson := i * 2 + 2   // The right child 
	//  Save the subscript of the maximum value 
	if lson < n && arr[largest] < arr[lson] {
    
		largest = lson
	}
	if rson < n && arr[largest] < arr[rson] {
    
		largest = rson
	}
	if largest != i {
    
		arr[largest], arr[i] = arr[i], arr[largest]
		//  Recursively maintain the heap to the child node 
		heapify(arr, n, largest)
	}
}

q347 front k High frequency elements

Subject portal

Answer key

First, use one hash Table to record the number of times each number appears , Then open a two-dimensional array ,count[i][0] Used to store the elements of a given array ,count[i][1] Used to store the number of occurrences of a given array element . Then use heap sorting , Sort the elements according to the number of occurrences , According to count[i][1] To build a small root pile , In order to count Array to sort . And then count[i][0] Deposit in res in , Finally, when len(nums) - i == k when , return res that will do . The practice is similar to the previous question .

func topKFrequent(nums []int, k int) []int {
    
	hashTable := make(map[int]int)
	for _, v := range nums {
    
		hashTable[v]++
	}
	var count [][]int
	for k, v := range hashTable {
    
		count = append(count, []int{
    k, v})
	}
	res := make([]int, 0)
	//  Building the heap 
	for i := len(count) / 2 - 1; i >= 0; i-- {
    
		heapify(count, len(count), i)
	}
	for i := len(count) - 1; i >= 0; i-- {
    
		count[i], count[0] = count[0], count[i]
		heapify(count, i, 0)
		res = append(res, count[i][0])
		if len(count) - i == k {
    
			break
		}
	}
	return res
}

func heapify(arr [][]int, n int, i int) {
    
	// Heap maintenance 
	largest := i  		//i Is the subscript of the current parent node 
	lson := i * 2 + 1   // Left the child 
	rson := i * 2 + 2   // The right child 
	//  Save the subscript of the maximum value 
	if lson < n && arr[largest][1] < arr[lson][1] {
    
		largest = lson
	}
	if rson < n && arr[largest][1] < arr[rson][1] {
    
		largest = rson
	}
	if largest != i {
    
		arr[largest], arr[i] = arr[i], arr[largest]
		//  Recursively maintain the heap to the child node 
		heapify(arr, n, largest)
	}
}