Topic describes

Given an array nums, for each element nums[I], count all the numbers in the array smaller than it. In other words, for each nums[I] you must calculate the number of valid js, where j satisfies j! = I and nums[j] < nums[I] Returns the answer as an array.

Example 1

Input: nums = [8,1,2,2,3] output: [4,0,1,1,3] explanation: there are four numbers smaller than nums[0]=8: (1,2,2, and 3). There is no number smaller than nums[1]=1. There exists a number smaller than nums[2]=2 :(1). There exists a number smaller than nums[3]=2 :(1). There exist three numbers smaller than nums[4]=3 :(1,2 and 2).Copy the code

Example 2

Input: nums = [6,5,4,8] output: [2,1,0,3]Copy the code

Example 3

Input: nums = [7,7,7] output: [0,0,0,0]Copy the code

prompt

  • 2 <= nums.length <= 500
  • 0 <= nums[i] <= 100

Answer key

package main

import (
	"fmt"
	"sort"
)

func main(a) {
	nums := [][]int{{8.1.2.2.3}, {6.5.4.8}, {7.7.7.7}}
	for _, data := range nums {
		fmt.Println(smallerNumbersThanCurrent(data))
	}
}

type pair struct {
	Pos   int
	Value int
}

// Quicksort
func smallerNumbersThanCurrent(nums []int) []int {
	p := make([]pair, len(nums))
	for i, num := range nums {
		p[i] = pair{i, num}
	}
	sort.Slice(p, func(i, j int) bool { return p[i].Value < p[j].Value })

	res := make([]int.len(nums))
	var small int
	for i := range p {
		if i > 0&& p[i].Value ! = p[i- 1].Value {
			small = i
		}
		res[p[i].Pos] = small
	}

	return res
}

// Count sort
func smallerNumbersThanCurrent1(nums []int) []int {
	cnt := [101]int{}
    for _, v := range nums {
        cnt[v]++
    }
    for i := 0; i < 100; i++ {
		cnt[i+1] += cnt[i]
	}

    res := make([]int.len(nums))
    for i, v := range nums {
        if v > 0 {
            res[i] = cnt[v- 1]}}return res
}
Copy the code