Four golang solutions with explanation and images
The main idea of the first two solutions is to add all the numbers to a matrix of lengths [len(nums)][2] and then sort each frequency of numbers by the max freq
The main idea of the first two solutions is to add all the numbers to a matrix of lengths `[len(nums)][2]` and then sort each frequency of numbers by the max frequency. Suppose two values have the same frequency sort them by the value in descending order. After they are sorted, add all the values back to `nums` and return `nums`.\n\n**This is the sort:**\n\n```\nfor i := 1; i < len(arr); i++ {\n    if i >= 1 && ((arr[i-1][0] > arr[i][0]) || \n    (arr[i-1][0] == arr[i][0] && arr[i-1][1] < arr[i][1])) {\n        arr[i], arr[i-1] = arr[i-1], arr[i]\n        i -= 2\n    }\n}\n```\n\nThe idea of it is to start at the second item (first if 0 indexed) and then check whether the frequency of the number before the current is greater than the frequency of the current number. This is show like this in the code: `((arr[i-1][0] > arr[i][0])`. Or it checks whether the frequency is the same and whether the current number is greater than the number before the current number, this is show in the code as this: `arr[i-1][0] == arr[i][0] && arr[i-1][1] < arr[i][1]`. If either of these things is true, then switch the current and number before the current element and subtracts `2` from `i`. We subtract `2` from `i` to move back if we have to switch the next current and number before the current numbers. And we subtract `2`, not `1` because the loops `i++` cancel out one of the subtracts. Since we have an `i -= 2`, we have to check whether `i >= 1` because if we don\'t and `i == 0`, we would have an out-of-bounds exception.\n\nIf you dont understand the explaination look at these images:\n\n![image](https://assets.leetcode.com/users/images/e0b432c2-5e05-42c8-951a-d67656b5db84_1614805285.342058.png)\n![image](https://assets.leetcode.com/users/images/5bdfb469-9333-4f88-a75d-c4053c0ce778_1614805285.3951283.png)\n![image](https://assets.leetcode.com/users/images/56115be1-93b3-4a63-85dc-8fd07f852d06_1614805285.5365767.png)\n\n\n\nThe second code has better space complexity because in the first solution we use a `map` of size `len(nums)` and an `array` of size `[len(nums)][2]`. In the second solution we just use an `array` of size `[len(nums)][2]`.\n\n\n\n**Code One:**\n\n``` go\nfunc frequencySort(nums []int) []int {\n    m := make(map[int]int)\n    arr := [][]int{}\n    counter := 0\n\n    for _, num := range nums {\n        m[num]++\n    }\n    for i, i2 := range m {\n        arr = append(arr, []int{i2, i})\n    }\n\n    for i := 1; i < len(arr); i++ {\n        if i >= 1 && ((arr[i-1][0] > arr[i][0]) || \n        (arr[i-1][0] == arr[i][0] && arr[i-1][1] < arr[i][1])) {\n            arr[i], arr[i-1] = arr[i-1], arr[i]\n            i -= 2\n        }\n    }\n\n    for i := 0; i < len(arr); i++ {\n        for j := 0; j < arr[i][0]; j++ {\n            nums[counter] = arr[i][1]\n            counter++\n        }\n    }\n\n    return nums\n}\n```\n\n**Code Two:**\n\n``` go\nfunc frequencySort(nums []int) []int {\n    arr := [][]int{}\n    counter := 0\n\n    for _, num := range nums {\n        contains := false\n\n        for _, ints := range arr {\n            if ints[1] == num {\n                ints[0]++\n                contains = true\n                break\n            }\n        }\n\n        if !contains {\n            arr = append(arr, []int{1, num})\n        }\n    }\n\n    for i := 1; i < len(arr); i++ {\n        if i >= 1 && ((arr[i-1][0] > arr[i][0]) ||\n        (arr[i-1][0] == arr[i][0] && arr[i-1][1] < arr[i][1])) {\n            arr[i], arr[i-1] = arr[i-1], arr[i]\n            i -= 2\n        }\n    }\n\n    for i := 0; i < len(arr); i++ {\n        for j := 0; j < arr[i][0]; j++ {\n            nums[counter] = arr[i][1]\n            counter++\n        }\n    }\n\n    return nums\n}\n```\n\nThe idea of the third and fourth solutions are pretty similar to each other. The main difference is that in the third solution we use `sort.Slice`, while in the fourth solution we use a heap.\n\n\n``` go\nfunc frequencySort(nums []int) []int {\n    m := make( map[int] int ) // map[val] index in arr\n    arr := [][]int{}\n    res := []int{}\n    \n    for _, num := range nums {\n        if _, ok := m[num]; !ok {\n            arr = append(arr, []int{})\n            m[num] = len(arr) - 1\n        }\n        arr[m[num]] = append(arr[m[num]], num)\n    }\n    \n    sort.Slice(arr, func(i, j int) bool {\n        if len(arr[i]) == len(arr[j]) { return arr[i][0] > arr[j][0] }\n        return len(arr[i]) < len(arr[j])\n    })\n    \n    for _, a := range arr {\n        res = append(res, a...)\n    }\n    \n    return res\n}\n```\n\n``` go\nfunc frequencySort(nums []int) []int {\n    m := make( map[int] []int )\n    h := &IntHeap{}\n    res := []int{}\n    for _, num := range nums {\n        m[num] = append(m[num], num)\n    }\n    \n    for _, b := range m {\n        heap.Push(h, b)\n    }\n    \n    for h.Len() > 0 {\n        res = append(res, heap.Pop(h).([]int)...)\n    }\n    \n    return res\n}\n\ntype IntHeap [][]int\n\nfunc (h IntHeap) Len() int           { return len(h) }\nfunc (h IntHeap) Less(i, j int) bool { \n    if len(h[i]) == len(h[j]) {\n        return h[i][0] > h[j][0]\n    }\n    return len(h[i]) < len(h[j]) \n}\nfunc (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }\n\nfunc (h *IntHeap) Push(x interface{}) {\n\t*h = append(*h, x.([]int))\n}\n\nfunc (h *IntHeap) Pop() interface{} {\n\told := *h\n\tn := len(old)\n\tx := old[n-1]\n\t*h = old[0 : n-1]\n\treturn x\n}\n```\n
['Go']