Сколько чисел меньше, чем текущее решение Leetcode


Сложный уровень Легко
Часто спрашивают в саман Амазонка Bloomberg
массив хеширования

Постановка задачи

В этой задаче нам дается массив. Для каждого элемента этого массива мы должны узнать количество элементов, меньших, чем этот элемент.
т.е. для каждого i (0 <= i

Пример

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).

nums = [6,5,4,8]
[2,1,0,3]

Подход (Грубая сила)

Мы можем просто запустить цикл для каждого элемента, начиная слева направо.
Для каждого элемента мы найдем количество элементов, которые меньше текущего числа.
Таким образом, мы запускаем один внешний цикл для каждого элемента, а во внутреннем цикле мы будем обходить весь массив, чтобы считать каждый элемент меньше текущего значения.

Реализация того, сколько чисел меньше текущего решения Leetcode

Программа C ++

#include <bits/stdc++.h>
using namespace std;

vector<int> smallerNumbersThanCurrent(vector<int>& nums) 
{
    vector<int> ans;

    for(int i=0;i<nums.size();i++)
    {
        int val=nums.at(i),count=0;
        for(int j=0;j<nums.size();j++)
        {
            if(nums.at(j)<val)  count++;
        }
        ans.push_back(count);
    }

    return ans;
}

int main() 
{
    vector<int> nums{ 8 , 1, 2 , 2 , 3 }; 
    vector<int> ans=smallerNumbersThanCurrent(nums);
    
    for(auto val:ans) cout<<val<<" ";
    cout<<endl;
    
    return 0;  
}
4 0 1 1 3

Программа Java

import java.lang.*;

class Rextester
{  
    public static int[] smallerNumbersThanCurrent(int[] nums) 
    {
        int[]ans=new int[nums.length];

        for(int i=0;i<nums.length;i++)
        {
            int count=0;
            for(int j=0;j<nums.length;j++)
            {
                if(nums[i]>nums[j])   count++;
            }
            ans[i]=count;
        }

        return ans;
    }
    
    public static void main(String args[])
    {
       int[]nums={8,1,2,2,3};  
       int[]ans=smallerNumbersThanCurrent(nums);
        
       for(int num:ans)  
       {
           System.out.print(num+" ");
       }
        
    }
}
4 0 1 1 3

Анализ сложности для определения того, сколько чисел меньше текущего решения Leetcode

Сложность времени

О (п ^ 2): Мы используем вложенный цикл, каждый из которых выполняется для длины n. Следовательно, временная сложность будет O (n ^ 2).

Космическая сложность 

О (1): Мы только что использовали массив длины n, чтобы вернуть ответ. Кроме того, мы не использовали дополнительную память. Так что сложность пространства постоянна.

Подход (оптимизированный)

Как мы знаем, число, меньшее, чем любой элемент в массиве, равно количеству чисел, меньших или равных этому числу-1.
Мол, в массиве
1 2 3 4 4 5
count of numbers less than 5 - это количество чисел, меньших или равных 4.
Итак, если мы каким-то образом сохраним счетчик каждого элемента, присутствующего в данном массиве, то мы можем легко сказать, сколько элементов меньше его.

Сколько чисел меньше, чем текущее решение Leetcode

Итак, мы сохраняем массив счетчиков размером 101. (потому что число может быть между [0,100])
каждый индекс массива count i будет говорить о вхождении числа i в данном массиве.

Теперь, чтобы узнать, сколько чисел меньше или равно числу в позиции, мы должны применить префиксную сумму.
Итак, мы применим префиксную сумму к массиву count.

Тогда для каждого элемента i массива количество элементов меньше этого числа будет count [i-1].

Итак, в этом подходе сначала мы создадим наш массив count.
Затем мы преобразуем его в сумму префикса.
Тогда для каждого элемента num входного массива у нас будет count [num-1].

Реализация того, сколько чисел меньше текущего решения Leetcode

Программа C ++

#include <bits/stdc++.h>
using namespace std;

vector<int> smallerNumbersThanCurrent(vector<int>& nums) 
{
    int count[101];
    memset(count,0,sizeof(count));
    for(auto& i:nums)
    {
        count[i]++;
    }

    for(int i=1;i<=100;i++)
    {
        count[i]=count[i-1]+count[i];
    }

    vector<int> ans;

    for(int i=0;i<nums.size();i++)
    {
        if(nums[i]==0)    ans.push_back(0);
        else    ans.push_back(count[nums[i]-1]);
    }

    return ans;
}

int main() 
{
    vector<int> nums{ 8 , 1, 2 , 2 , 3 }; 
    vector<int> ans=smallerNumbersThanCurrent(nums);
    
    for(auto val:ans) cout<<val<<" ";
    cout<<endl;
    
    return 0;  
}
4 0 1 1 3

Программа Java

#include <bits/stdc++.h>
using namespace std;

vector<int> smallerNumbersThanCurrent(vector<int>& nums) 
{
    int count[101];
    memset(count,0,sizeof(count));
    for(auto& i:nums)
    {
        count[i]++;
    }

    for(int i=1;i<=100;i++)
    {
        count[i]=count[i-1]+count[i];
    }

    vector<int> ans;

    for(int i=0;i<nums.size();i++)
    {
        if(nums[i]==0)    ans.push_back(0);
        else    ans.push_back(count[nums[i]-1]);
    }

    return ans;
}

int main() 
{
    vector<int> nums{ 8 , 1, 2 , 2 , 3 }; 
    vector<int> ans=smallerNumbersThanCurrent(nums);
    
    for(auto val:ans) cout<<val<<" ";
    cout<<endl;
    
    return 0;  
}
4 0 1 1 3

Анализ сложности для определения того, сколько чисел меньше текущего решения Leetcode

Сложность времени

O (макс (n, 100)): Сложность по времени будет O (Max (n, 100)), где n - размер входного массива, а 100 берется, потому что мы создаем дополнительный массив размером 100, который также проходит.

Космическая сложность 

О (1): Мы используем дополнительный массив счетчиков размером 100, поэтому сложность пространства постоянна.