leetcode第1365题（简单）

原链接：https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/

问题描述

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例1

输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释： 
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。 
对于 nums[3]=2 存在一个比它小的数字：（1）。 
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例2

输入：nums = [6,5,4,8]
输出：[2,1,0,3]

示例3

输入：nums = [7,7,7,7]
输出：[0,0,0,0]

解题思路

构造单向链表。

构造一个有序的单向链表 结构 如下：

private class Node{
        public int val;//当前值
        public int index;//当前下标
        public Node next;
        public Node(int val,int index){
            this.val=val;
            this.index=index;
        }
    }

链表节点，不保存原数组中的值，只保存有序状态下，原数组的位置（顺序的位置）。

先将原数组的所有数据添加到链表中（添加过程中保证 链表中的数据是有序的）

val保存原数组中大于当前节点值得个数，即也是当前节点前面的所有节点大于当前节点的个数，

例如链表 1->2->5->6 当前节点为5，那么当前节点的val值就是2，因为节点5前面有两个节点比5小，如果知道当前节点的val值，那么通过比较当前节点nums[index]和下一个节点的nums[index]就可以推算出下一个节点的val

那么如此以来就可以方便的从头节点开始推算出每个节点的val，再次通过遍历这个链表，就可以得出原数组中每个位置有多少小于当前数字的值。

代码（java）

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        return begin(nums);
    }
    public int[] begin(int[] nums){
        if(nums==null){
            return null;
        }
        int[] b = new int[nums.length];
        Node head=new Node(nums[0],0);
        for(int i=1;i<nums.length;i++){
            head=add(head,new Node(nums[i],i));
        }
        int u=1;
        while(head.next!=null){
            if(head.next.val==head.val){
                b[head.next.index]=b[head.index];
            }else{
                b[head.next.index]=u;
            }
            u++;
            head=head.next;
        }
        return b;
    }
    public Node add(Node head,Node node){
        Node h=head;
        Node p=null;
        while(head!=null&&node.val>head.val){
            p=head;
            head=head.next;
        }
        node.next=head;
        if(p!=null){
            p.next=node;
        }else{
            h=node;
        }
        return h;
    }
    private class Node{
        public int val;//当前值
        public int index;//当前下标
        public Node next;
        public Node(int val,int index){
            this.val=val;
            this.index=index;
        }
    }
}