当前位置:网站首页>LeetCode 6006. Take out the least number of magic beans
LeetCode 6006. Take out the least number of magic beans
2022-07-06 00:09:00 【Daylight629】
6006. Take out the smallest number of magic beans
To give you one just An array of integers beans
, Each integer represents the number of magic beans in a bag .
Please... From each bag take out Some beans ( It's fine too Don't take out ), Make the rest Non empty In the bag ( namely At least also One Magic bean bag ) Number of magic beans equal . Once the magic beans are removed from the bag , You can't put it in any other bag .
Please return to where you need to take out the magic beans Minimum number .
Example 1:
Input :beans = [4,1,6,5]
Output :4
explain :
- We never had 1 Take it out of a magic bean bag 1 A magic bean .
The number of magic beans left in the bag is :[4,0,6,5]
- Then we have 6 Take it out of a magic bean bag 2 A magic bean .
The number of magic beans left in the bag is :[4,0,4,5]
- Then we have 5 Take it out of a magic bean bag 1 A magic bean .
The number of magic beans left in the bag is :[4,0,4,4]
A total of 1 + 2 + 1 = 4 A magic bean , The number of magic beans left in the non empty bag is equal .
Nothing is better than taking out 4 A plan with fewer magic beans .
Example 2:
Input :beans = [2,10,3,2]
Output :7
explain :
- We never had 2 Take it out of one of the bags of magic beans 2 A magic bean .
The number of magic beans left in the bag is :[0,10,3,2]
- Then we have... From another 2 Take it out of a magic bean bag 2 A magic bean .
The number of magic beans left in the bag is :[0,10,3,0]
- Then we have 3 Take it out of a magic bean bag 3 A magic bean .
The number of magic beans left in the bag is :[0,10,0,0]
A total of 2 + 2 + 3 = 7 A magic bean , The number of magic beans left in the non empty bag is equal .
Nothing is better than taking out 7 A plan with fewer magic beans .
Tips :
1 <= beans.length <= 105
1 <= beans[i] <= 105
Two 、 Method 1
Sort + The prefix and
class Solution {
public long minimumRemoval(int[] beans) {
long res = Long.MAX_VALUE;
long sum = 0;
Arrays.sort(beans);
for (int i = 0; i < beans.length; i++) {
sum += beans[i];
}
for (int i = 0; i < beans.length; i++) {
long temp = 0;
temp += sum - (long)(beans.length - i) * beans[i];
res = Math.min(res, temp);
}
return res;
}
}
Complexity analysis
Time complexity :O(nlogn).
Spatial complexity :O(1).
边栏推荐
- openssl-1.0.2k版本升级openssl-1.1.1p
- Ffmpeg learning - core module
- What is information security? What is included? What is the difference with network security?
- Tools to improve work efficiency: the idea of SQL batch generation tools
- 14 MySQL view
- 【NOI模拟赛】Anaid 的树(莫比乌斯反演,指数型生成函数,埃氏筛,虚树)
- Huawei equipment is configured with OSPF and BFD linkage
- What are Yunna's fixed asset management systems?
- 【DesignMode】组合模式(composite mode)
- DEJA_ Vu3d - cesium feature set 055 - summary description of map service addresses of domestic and foreign manufacturers
猜你喜欢
[online chat] the original wechat applet can also reply to Facebook homepage messages!
FFMPEG关键结构体——AVFormatContext
Online yaml to CSV tool
Huawei equipment configuration ospf-bgp linkage
Recognize the small experiment of extracting and displaying Mel spectrum (observe the difference between different y_axis and x_axis)
What are the functions of Yunna fixed assets management system?
如何解决ecology9.0执行导入流程流程产生的问题
Key structure of ffmpeg - avformatcontext
18.(arcgis api for js篇)arcgis api for js点采集(SketchViewModel)
Laser slam learning record
随机推荐
亲测可用fiddler手机抓包配置代理后没有网络
wx.getLocation(Object object)申请方法,最新版
Learn PWN from CTF wiki - ret2libc1
How to rotate the synchronized / refreshed icon (EL icon refresh)
How much do you know about the bank deposit business that software test engineers must know?
Configuring OSPF load sharing for Huawei devices
Global and Chinese markets for pressure and temperature sensors 2022-2028: Research Report on technology, participants, trends, market size and share
DEJA_VU3D - Cesium功能集 之 055-国内外各厂商地图服务地址汇总说明
Mysql - CRUD
Laser slam learning record
【luogu P3295】萌萌哒(并查集)(倍增)
openssl-1.0.2k版本升级openssl-1.1.1p
Huawei equipment configuration ospf-bgp linkage
数据库遇到的问题
FFMPEG关键结构体——AVCodecContext
[QT] QT uses qjson to generate JSON files and save them
认识提取与显示梅尔谱图的小实验(观察不同y_axis和x_axis的区别)
Global and Chinese markets of POM plastic gears 2022-2028: Research Report on technology, participants, trends, market size and share
USB Interface USB protocol
[SQL] SQL expansion languages of mainstream databases (T-SQL, pl/sql, pl/pgsql)