※ 引述 《sustainer123 (caster)》 之銘言：
:
: https://leetcode.com/problems/height-checker
:
: 1051. Height Checker
:
: 給定一數列heights 我們期待heights是一非遞減數列
:
: 此理想數列設為expected
:
: 請回傳heights[i] != expected[i]的數量
:
:
: Example 1:
:
: Input: heights = [1,1,4,2,1,3]
: Output: 3
: Explanation:
: heights: [1,1,4,2,1,3]
: expected: [1,1,1,2,3,4]
: 推 DJYOSHITAKA: bucket吧 但我好懶 06/10 09:57
bucket的思路:
塞進去之後
從最小的數到最大的
同時看原本的陣列裡面有哪裡不一樣
class Solution {
public:
int heightChecker(vector<int>& heights)
{
int len = heights.size();
vector<int> paper(101,0);
for(int k : heights)
{
paper[k]++;
}
int ans = 0;
int p = 0;
for(int i = 0 ; i < 101 ; i ++)
{
for(int j = 0 ; j < paper[i] ; j ++)
{
if(heights[p] != i)ans ++;
p++;
}
}
return ans;
}
};