Leetcode question brushing (II) -- sorting (go Implementation)

leetcode Question brushing and sorting series

leetcode Brush problem ( One ) — Two pointer thought
leetcode Brush problem ( Two ) — Sequencing ideas
leetcode Brush problem ( 3、 ... and ) — Dichotomous thinking
leetcode Brush problem ( Four ) — Greedy thoughts

 

leetcode Brush question type （ Two ）--- Sort type

• solve Kth Element problem , That is the first. K The question of elements
• solve TopK Elements problem , That is to say K A question of the smallest elements

solution ：

1. With the help of quick sort
2. With the help of the minimum heap
    

215 The first K The question of elements

215 The... In the array K The biggest element

Given an array of integers nums And integer k, Please return the... In the array k The biggest element .
Please note that , What you need to look for is the number after array sorting k The biggest element , Not the first. k A different element .

Solution 1 : With the help of quick sort

   This kind of topic can use the quick sort partition() Search for

   In an increasing array , The first K The subscript of a large element is N-K, So just before the array N-K You can increase the number of elements in order .

hypothesis partion() The position of the return element is j, that j The element of location >= j The element on the left

• If j = N-K, that j The position element is the first K Big element
• If j < N-K, So the first K The big element is on the right , The new left boundary is j+1
• If j > N-K, So the first K The big element is on the left , The new right boundary is j-1

func findKthLargest(nums []int, k int) int {
    
    rand.Seed(time.Now().UnixNano())
    return quickSelect(nums, 0, len(nums)-1, len(nums)-k)
}

func quickSelect(arr []int, left, right, target int) int {
    
    j := randomPartition(arr, left, right)
    //target namely N-K
    if j == target {
    
        return arr[j]
    } else if j < target {
       //j < N-K, So the first K The big element is on the right , The new left boundary is j+1
        return quickSelect(arr, j+1, right, target)
    }
    return quickSelect(arr, left, j-1, target)   //j > N-K, So the first K The big element is on the left , The new right boundary is j-1
}

func randomPartition(arr []int, left, right int) int {
    
    // avoid partion It will degenerate into O(N)
    i := rand.Int() % (right - left + 1) + l  // rand Intn The generated is [0,（right-left+1）] Value , So add 1
    arr[i], arr[right] = arr[right], arr[i]
    return partition(arr, left, right)
}

func partition(arr []int,left int,right int)  int {
    
	i:=left+1  // Left pointer 
	j:=right   // Right pointer 
  
  // Default and arr[left] For division , Final ratio arr[left] The small one is on its left , Than arr[left] The big one is on its right 
	for true{
    
		for i<right {
    
			if arr[i]>flag {
     // Find a comparison arr[left] Big value , If you can't find it, move to the right and look for it 
				break
			}
			i++
		}
		for j>left {
       // Find a comparison arr[left] Small value , If you can't find it, move left and look for it 
			if  arr[j]<flag {
    
				break
			}
			j--
		}
		// Can't find 
		if i>=j {
    
			break
		}
		// eureka , swapping 
    arr[i], arr[j] = arr[j], arr[i]
	}
	// here ,arr[left]<arr[j]<arr[i]
	arr[left], arr[j] = arr[j], arr[left]
	return j
}

 

Solution 2 ： With the help of the minimum heap

   With the help of the minimum heap , Put all the elements in the smallest heap , then pop Out N-K Elements , At this time, only... Is left in the heap K Elements , The top of the heap element is the second K Big element .

  go Provided in container/heap To implement heap , The types of elements in the heap need to implement heap.Interface This interface .

The biggest pile ：func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
The smallest pile ：func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }

type IntHeap []int

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{
    }) {
    
	*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{
    } {
    
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func findKthLargest(nums []int, k int) int {
    
	h := &IntHeap{
    }
	heap.Init(h)
	for _,v:=range nums{
       // Put all the elements in the heap 
		heap.Push(h,v)
	}
	if k < len(nums) {
    
		for i:=0;i<len(nums)-k;i++{
      // eject N-K Elements 
			heap.Pop(h)
		}

	}
	return heap.Pop(h).(int)    // At this time, the top element of the stack is the K Big element 
}

K When the smallest element is returned, the array is returned [0:N-K] Or heaped N-K To the last element in the heap

 

347 The most frequent k Elements

Solution 1 ： With maximum heap

   First, traverse the entire array , And use a hash table to record the number of occurrences of each number , And form a 「 Number of occurrences array 」. Find the front of the original array k High frequency elements , It's equivalent to finding out 「 Number of occurrences array 」 Before k Big value , Then iterate over the value of the occurrence array , Insert into the maximum heap , The front... Ejected from the heap k Elements are the most frequent k Elements .

   If the maximum heap is built only according to the number of occurrences , After getting the heap element, it is impossible to know which element the occurrence belongs to , So each node in the heap not only needs to save the number of occurrences of the element （count）, You also need to save which element the number of times belongs to （value). You can put both in Item in , With Item As a node of the heap .

type Item struct {
    
	value int  // Storage elements 
	count int  // The number of occurrences of the storage element 
}
type IntHeap []*Item   // Each node in the heap stores one Item, Contains the element and the number of occurrences of the element 

func (h IntHeap) Len() int           {
     return len(h) }
func (h IntHeap) Less(i, j int) bool {
     return h[i].count > h[j].count }   // Build the maximum heap based on the number of occurrences of the element 
func (h IntHeap) Swap(i, j int)      {
     h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{
    }) {
    
	*h = append(*h, x.(*Item))
}
func (h *IntHeap) Pop() interface{
    } {
    
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func main()  {
    
	arr:=[]int{
    1,1,1,2,2,3}
	fmt.Println(topKFrequent(arr,2))
}


func topKFrequent(nums []int, k int) []int {
    
	res := make([]int,k)
	m:=make(map[int]int)
	for _,v := range nums {
      // Traverse the array to count the number of occurrences of each element 
		m[v]++
	}
	h:=&IntHeap{
    }
	heap.Init(h)
	for value,count := range m {
    
		heap.Push(h,&Item{
    value,count})    // Every one of them map Data as a Item Into the heap 
	}
	for i:=0;i<k;i++ {
         // The heap top element is the maximum , I.e. the most times , So pop up before k The top elements of the heap are the top elements that appear the most k Elements 
		res[i]=heap.Pop(h).(*Item).value   // In the top element of the heap value, That is, the initial array elements are added to the returned array 
	}
	return res
}

 

451 Sort the characters according to their frequency of occurrence

  Given a string , Please arrange the characters in the string in descending order of frequency .

and 347 similar , Build the largest heap , Determine the order and number of characters in the returned string according to the heap top element .

type Item struct {
    
	value byte  // Store characters 
	count int  // Store the number of occurrences of characters 
}
type IntHeap []*Item   // Each node in the heap stores one Item, Contains the element and the number of occurrences of the element 

func (h IntHeap) Len() int           {
     return len(h) }
func (h IntHeap) Less(i, j int) bool {
     return h[i].count > h[j].count }   // Build the maximum heap based on the number of occurrences of the element 
func (h IntHeap) Swap(i, j int)      {
     h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{
    }) {
    
	*h = append(*h, x.(*Item))
}
func (h *IntHeap) Pop() interface{
    } {
    
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func frequencySort(s string) string {
    
	arr:=[]byte(s)
	var res []byte
	m:=make(map[byte]int)
	for _,v := range arr {
      // Traverse the array to count the number of occurrences of each element 
		m[v]++
	}
	h:=&IntHeap{
    }
	heap.Init(h)
	for value,count := range m {
    
		heap.Push(h,&Item{
    value,count})    // Every one of them map Data as a Item Into the heap 
	}
	for h.Len()>0 {
    
		item:=heap.Pop(h).(*Item)
		for i:=item.count;i>0;i--{
       // Pop up top element , It appears several times append How many times res Array 
			res = append(res,item.value)
		}
	}
	return string(res)
}

 

75 Color classification

   Give one that contains red 、 White and blue , altogether n Array of elements , Sort them in place , Make elements of the same color adjacent , And follow the red 、 white 、 In blue order .
   In this question , We use integers 0、 1 and 2 Red... Respectively 、 White and blue .

Solution 1 ： violence

   Count the numbers in the array 0, 1, 20,1,2 The number of , Then according to their number , Overwrite the entire array
 

Solution 2 ： Double pointer

  All of the 0 Swap to the head of the array
  All of the 2 Swap to the end of the array

func sortColors(nums []int)  {
    
	p0, p2 := 0, len(nums)-1
	for i := 0; i <= p2; i++ {
    
		for ; i <= p2 && nums[i] == 2; p2-- {
         //nums[i] by 2 To the end of the array 
			nums[i], nums[p2] = nums[p2], nums[i]
		}
		if nums[i] == 0 {
        // After exchanging nums[i] by 0, Swap to array header 
			nums[i], nums[p0] = nums[p0], nums[i]
			p0++
		}
	}
}

 
 
If there is any wrong , Please point out , thank ~
 
Reference from ：
http://www.cyc2018.xyz/
https://leetcode-cn.com/problems