LeetCode: recuento de números más pequeños después de uno mismo (Java)

Se le proporciona una matriz de números enteros y debe devolver una nueva matriz de conteos. La matriz de conteos tiene la propiedad donde cuenta[i] es el número de elementos más pequeños a la derecha de nums[i].

Ejemplo:

Aporte: [5,2,6,1]

Producción: [2,1,1,0]

Solución Java 1

public List<Integer> countSmaller(int[] nums) {
    List<Integer> result = new ArrayList<Integer>();
    ArrayList<Integer> sorted = new ArrayList<Integer>();
 
    for(int i=nums.length-1; i>=0; i--){
        if(sorted.isEmpty()){
            sorted.add(nums[i]);
            result.add(0);
        }else if(nums[i]>sorted.get(sorted.size()-1)){
            sorted.add(sorted.size(), nums[i]);
            result.add(sorted.size()-1);
        }else{
            int l=0; 
            int r=sorted.size()-1;
 
            while(l<r){
                int m = l + (r-l)/2;
 
                if(nums[i]>sorted.get(m)){
                    l=m+1;
                }else{
                    r=m;
                }
            }
 
            sorted.add(r, nums[i]);
            result.add(r);
        }    
    }
 
    Collections.reverse(result);
 
    return result;
}

Esta solucion es simple. Sin embargo, tenga en cuenta que la complejidad temporal de agregar un elemento a una lista es O (n), porque los elementos posteriores a la posición de inserción deben cambiarse. Entonces, la complejidad del tiempo es O (n ^ 2 (logn)).

Solución Java 2

Si queremos usar la búsqueda binaria y definir una estructura como la siguiente:

LeetCode - Cambio de moneda (Java)

En promedio, la complejidad del tiempo es O (n * log (n)) y la complejidad del espacio es O (n).

class Solution {
    public List<Integer> countSmaller(int[] nums) {
 
        List<Integer> result = new ArrayList<Integer>();
        if(nums==null || nums.length==0){
            return result;
        }
 
        Node root = new Node(nums[nums.length-1]);
        root.count=1;
        result.add(0);
 
        for(int i=nums.length-2; i>=0; i--){
            result.add(insertNode(root, nums[i]));
        }
 
        Collections.reverse(result);
 
        return result;
    }
 
    public int insertNode(Node root, int value){
        Node p=root;
        int result=0;
 
        while(p!=null){
            if(value>p.value){
                result+=p.count+p.numLeft;
                if(p.right==null){
                    Node t = new Node(value);
                    t.count=1;
                    p.right=t;
                    return result;
                }else{
                    p=p.right;
                }
            }else if(value==p.value){
                p.count++;
                return result+p.numLeft;
            }else{
                p.numLeft++;
 
                if(p.left==null){
                    Node t = new Node(value);
                    t.count=1;
                    p.left=t;
                    return result;
                }else{
                    p=p.left;
                }
            }
        }
 
        return 0;
    }
}
 
class Node{
    Node left;
    Node right;
 
    int value;
    int count;
    int numLeft;
    public Node(int value){
        this.value=value;
    }
}

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta