###### tags: `Leetcode` `easy` `sort` `python` `c++`

# 1365. How Many Numbers Are Smaller Than the Current Number

## [題目連結:] https://leetcode.com/problems/how-many-numbers-are-smaller-than-the-current-number/description/

## 題目:
Given the array ```nums```, for each ```nums[i]``` find out how many numbers in the array are smaller than it. That is, for each ```nums[i]``` you have to count the number of valid ```j's``` such that ```j != i``` **and** **nums[j] < nums[i]**.

Return the answer in an array.

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

## 解題想法:
* 此題為求，對於每個nums[i]，找出數組中有多少個數小於它。
* 作法:
* 先排序
* 排序好後第一次出現的位子即為小於該數的總數

	nums=[8,1,2,2,3]
	tmp=sorted(nums)=[1,2,2,3,8]
	
	pos= 0 1 2 3 4 
	tmp= 1 2 2 3 8
	for pos,val in enumerate(nums):
		res[pos]=tmp.index(val)

## Python:

from collections import defaultdict
class Solution(object):
    def smallerNumbersThanCurrent(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        #sort+search
        #O(nlogn+n)
        res=[0 for _ in range(len(nums))]
        tmp=sorted(nums)
        #排序好後第一次出現的位子即為小於該數的總數
        for pos,val in enumerate(nums):
            res[pos]=tmp.index(val)
        return res

## C++:
* c++的vector沒有像python的list一樣可以使用index查元素的位置:"(

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> res(nums.size(),0);
        vector<int> tmp(nums);
        sort(tmp.begin(), tmp.end());
        for (int i=0; i<nums.size(); i++){
            for (int j=0; j<tmp.size(); j++){
                if (nums[i]==tmp[j]){
                    res[i]=j;
                    break;
                }
            }
        }
        return res;
    }
};