[PYTHON] Let Code Day53 Starting from Zero "1365. How Many Numbers Are Smaller Than the Current Number"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

Apparently, many engineers take measures on the site called LetCode.

It is a site that trains the algorithmic power that can withstand the coding test that is being done in the early story, and it is an inevitable path for those who want to build a career at an overseas tech company.

I wrote it in a big way, but I have no plans to have such an interview at the moment.

However, as an IT engineer, it would be better to have the same level of algorithm power as a person, so I would like to solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

I'm solving it with Python3.

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day52 starting from zero "1351. Count Negative Numbers in a Sorted Matrix"

Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

problem

1365. How Many Numbers Are Smaller Than the Current Number

The difficulty level is Easy. I will write it because it was a good problem.

The problem is given the array nums. The problem is to design an algorithm that leads each element in those arrays more times than the other elements. It's difficult in Japanese, so let's see an example.

Input: nums = [8,1,2,2,3] Output: [4,0,1,1,3] Explanation: For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3). For nums[1]=1 does not exist any smaller number than it. For nums[2]=2 there exist one smaller number than it (1). For nums[3]=2 there exist one smaller number than it (1). For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

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

Input: nums = [7,7,7,7] Output: [0,0,0,0]

solution

A simple idea is to associate it with the index.

It sorts nums, retrieves it with the original index in the for statement, and adds it to the array.

For example, if nums = [6,5,4,8] in the example The result of sorting is num = [4,5,6,8]. If you think about that element in the index, you can see it naturally. For num = [4,5,6,8], the index will be [0,1,2,3]. Replacing this in the order nums gives[2,1,0,3], which matches the example.

If you write this flow in Python, it will look like this.

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        ans = []
        num = sorted(nums)
        for i in range(len(nums)):
            ans.append(num.index(nums[i]))
        return ans
# Runtime: 92 ms, faster than 55.84% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.
# Memory Usage: 13.8 MB, less than 79.58% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.

If you write it more concisely, you can also write as follows.

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        sorted_nums = sorted(nums)
        return [sorted_nums.index(num) for num in nums]
# Runtime: 100 ms, faster than 54.35% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.
# Memory Usage: 13.9 MB, less than 41.13% of Python3 online submissions for How Many Numbers Are Smaller Than the Current Number.

There are some ways of thinking, but I thought this way of thinking was smarter. It's a good problem that you can solve smartly with a little twist, rather than thinking honestly.

So that's it for this time. Thank you for your hard work.