golang 刷 leetcode 前 K 個高頻元素

給你一個整數數組 nums 和一個整數 k ，請你返回其中出現頻率前 k 高的元素。你可以按 任意順序 返回答案。

示例 1:

輸入: nums = [1,1,1,2,2,3], k = 2

輸出: [1,2]

示例 2:

輸入: nums = [1], k = 1

輸出: [1]

提示：

1 <= nums.length <= 105

k 的取值範圍是 [1, 數組中不相同的元素的個數]

題目數據保證答案唯一，換句話說，數組中前 k 個高頻元素的集合是唯一的

進階：你所設計算法的時間複雜度 必須 優於 O(n log n) ，其中 n 是數組大小。

解法一：

解題思路

1，將數組轉化成數字、頻次對

2，對於 k 高頻的，我們可以採用小根堆，來做排序

func topKFrequent(nums []int, k int) []int {
   m:=make(map[int]int)
   for _,n:=range nums{
       m[n]++
   }
   h:=&heap{
       cap:k,
   }
   for k,v:=range m{
      h.push(d{num:k,count:v})
   }
   var v []int
   for _,i:=range h.data{
     v=append(v,i.num)
   }
   return v
}
type d struct{
        num int
        count int
}
type heap struct {
    data []d
    cap int
}
func (h*heap)push(da d){
   if len(h.data)>=h.cap{
       if da.count<=h.data[0].count{
           return
       }
       h.data[0]=da
       h.adjust(0)
       return
   }
    h.data=append(h.data,da)
   if len(h.data)==h.cap{
       for k:=h.cap/2;k>=0;k--{
           h.adjust(k)
       }
   }
}
func (h *heap)adjust(i int){
    for i<h.cap {
    l:=2*i+1
    r:=2*i+2
    if r<h.cap{
        if h.data[l].count<h.data[r].count &&  h.data[l].count< h.data[i].count{
            h.data[i],h.data[l]= h.data[l],h.data[i]
            i=l
        }else if  h.data[r].count< h.data[i].count{
             h.data[i],h.data[r]= h.data[r],h.data[i]
             i=r
        }else{
            break
        }
    }else if l< h.cap &&  h.data[l].count< h.data[i].count{
            h.data[i],h.data[l]= h.data[l],h.data[i]
            i=l
    }else{
        break
    }
    }
}

源碼：

解法二：

解題思路

1，將數組轉化成數字、頻次對

2，我們知道快速排序的複雜度是 nlogn，且每一次排序後，pivot 前面的元素都比 pivot 大，後面的都比 pivot 小

3，類比這個思路：

A，pivot==k,pivot 前面的元素就是所求，得解

B，pivot>k, 我們繼續在 0 到 pivot 之間尋找

C，pivot<k 我們在 pivot 和 len 之間尋找

4，所以可以結合快速排序來求結果

源碼：

func topKFrequent(nums []int, k int) []int {
  if len(nums)<=1{
      return nums
  }
  m:=make(map[int]int)
  for _,n:=range nums{
      m[n]++
  }
  var data []d
  for k,v:=range m{
    data=append(data,d{num:k,cnt:v})
  }
  fmt.Println(m,data)
  if len(data)<=k{
  return getNum(data)
  }
   adjust(data,0,len(data)-1,k)
  return getNum(data[:k])
}
func adjust(data[]d,start,end,t int){
    if start <0 ||end>len(data)-1{
        return 
    }
   l:=start
   r:=end
   for l<r{ 
        for l<r{ 
        if data[l].cnt>=data[r].cnt{
           r--
        }else{
            data[l],data[r]=data[r],data[l]
            break
        }
        }
        for l<r{  
         if data[r].cnt<=data[l].cnt{
            l++
        }else{
             data[r],data[l]=data[l],data[r]
             break
        }
        }
  }
  if l+1==t{
     return 
  }
  if l+1<t{
     adjust(data,l+1,end,t)
     return
  }
   adjust(data,start,r-1,t)
}
func getNum(da[]d)[]int{
    var  r []int
    for _,v:=range da{
       r=append(r,v.num)
    }
    return r
}
type d struct{
    num int
    cnt int
}

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/EksbdKuXyvYANNO1ZyDP-g