Leetcode 题解 315. Count of Smaller Numbers After Self

皮拉图斯 2020-06-16

770

点击上方“蓝字”关注！

计算数组中的每个元素后面比它小的数的个数. 这道 leetcode 的 hard 题，灵活的考察了对排序算法的理解.

题目分析

You are given an integer array nums and you have to return a 
new counts array. The counts array has the property where 
counts[i] is the number of smaller elements to the right of 
nums[i].


Example:


Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

题目的大意是给一个数组，返回数组中每个位置的元素，后面比它小的元素的个数.

不考虑时间复杂度，这个题目很容易做，暴力方法，从每个元素出发，遍历到结尾，记录比它小的元素个数. 这种方法的时间复杂度是 o(n^2).

进一步思考分析，如果将每个元素进行排序，从这个元素的后面交换到这个元素的前面的次数就是原数组中，该元素后面比它小的数量. 可以借助排序的思路解决该问题. 这里首先借用简单排序中的插入排序的思想.

考虑插入排序的过程，从倒数第一个开始，插入过程中. 该元素交换的次数就是该元素的结果值. 但是插入排序的时间复杂度是 o(n^2).

不过既然能用插入排序，那么其它排序的思想是否可以借用的. 首先，我们知道时间复杂度更低的排序算法有快速排序、希尔排序、归并排序和堆排序等，堆排序、快速排序、希尔排序都是不稳定排序，在这个问题中可能影响结果.而归并排序是稳定排序且时间复杂度是 o(nlog n).

下面将给出基于插入排序和归并排序思路的两种做法解题.

插入排序

这里的插入排序使用了借用了链表，其实也可以直接使用数组计算交换次数.

代码实现如下，基于 golang 语言实现. 这里从最后一个元素开始，不断的向链表中插入元素，在链表中元素按从小到大的顺序排序，这样插入过程中，向后遍历的元素数量，就是比它小的元素数量. 新元素插入链表后，返回头节点和插入的数量.

func countSmaller(nums []int) []int {
    res := make([]int, len(nums))
    var root *Node
    for i := len(nums) - 1; i >= 0 ;i -- {
        root, res[i] = insertData(root, nums[i])
    }
    return res
}


type Node struct{
    Next *Node
    Val int
}


func insertData(root *Node, n int) (*Node, int){
    if root == nil {
        return &Node{
            Val: n,
        }, 0
    }
    tmp := &Node{
        Val: n,
    }
    if tmp.Val <= root.Val {
        tmp.Next = root
        return tmp, 0
    }
    res := 0
    cur := root
    var pre *Node
    for cur != nil {
        if cur.Val < tmp.Val {
            pre = cur
            cur = cur.Next
            res++ 
        }else{
            break
        }
    }
    
    pre.Next = tmp
    tmp.Next = cur
    
    return root, res
}

归并排序

下面代码是在归并排序过程中计算将后面更小元素移动到前面的数量. 从而计算数组中每个元素后面更小的元素的数量.

为了更方便的计算原始元素位置的值后面比它小的元素的数量，避免元素交换乱序后，多次归并过程中的值无法累加.这里归并排序使用了辅助空间，以下标代替元素值，这样始终可以通过下标值将交换次数累加到原位置.

func countSmaller(nums []int) []int {
    indexes := make([]int, 0)
    res := make([]int, len(nums))
    for i, _ := range nums{
        indexes = append(indexes, i)
    }
    mergeSort(indexes, nums, res)
    return res
}


// 归并排序
func mergeSort(indexes, nums, res []int) []int{
    if len(indexes) <= 1{
        return indexes
    }
    
    m := len(indexes)  2
    left := mergeSort(indexes[:m], nums, res)
    right := mergeSort(indexes[m:], nums, res)
    
    sorted := make([]int, len(indexes))
    for i, j, k := 0, 0, 0; i < len(left) || j < len(right);{
        if i < len(left) && (j >= len(right) || nums[left[i]] <= nums[right[j]]){
            sorted[k] = left[i]
            res[left[i]] += j // 比下标在 left[i] 位置元素的h后面更小的数 +j
            i++
        } else{
            sorted[k] = right[j]
            j++
        }
        k++
    }
    
    return sorted
}

END

1. leetcode 原题目地址: [https://leetcode.com/problems/count-of-smaller-numbers-after-self/].

END

数据库

文章转载自皮拉图斯，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

Leetcode 题解 315. Count of Smaller Numbers After Self

评论