一、题目
给你一个长度为 n 的整数数组 coins ,它代表你拥有的 n 个硬币。第 i 个硬币的值为 coins[i] 。如果你从这些硬币中选出一部分硬币,它们的和为 x ,那么称,你可以 构造 出 x 。
请返回从 0 开始(包括 0 ),你最多能 构造 出多少个连续整数。
你可能有多个相同值的硬币。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/maximum-number-of-consecutive-values-you-can-make/description/
二、C解法
我的思路及代码
先使用快速排序算法对数组进行排序。然后用i作为计数器,判断当前的i是否可以被表示,直到不能被表示的时候退出。此代码在测试时由于超时未通过
- 时间复杂度:排序O(nlogn),查找O(n^2)
- 空间复杂度:排序需要O(logn)的栈空间
int Partition(int A[],int low,int high){
int pivot=A[low];//将第一个元素设置为枢纽
while (low<high){//循环跳出条件
while (low<high&&A[high]>=pivot) --high;//从后往前找到比枢纽元素小的元素
A[low] = A[high];//比枢纽小的元素移动到左边
while (low<high&&A[low]<=pivot) ++low;//从前往后找到比枢纽元素大的元素
A[high] = A[low];//比枢纽大的元素移动到右边
}
A[low]=pivot;//最后low和high重合的位置就是枢纽元素的位置
return low;//返回枢纽的位置
}
/**
* 快速排序
* @param A 待排序数组
*/
void QuickSort(int A[],int low,int high){
if(low<high){//递归跳出条件
int pivotpos = Partition(A,low,high);//第一次划分
QuickSort(A,low,pivotpos-1);//对两个子表进行划分
QuickSort(A,pivotpos+1,high);
}
}
int getMaximumConsecutive(int* coins, int coinsSize){
QuickSort(coins,0,coinsSize-1);
for(int i=1;;i++){//i就是要返回的数
int temp = i;
for(int j=coinsSize-1;j>=0;j--){
if(temp==coins[j]) {
if(coins[j]==1){
i+=j;
}
temp=0;break;
}
if(temp<coins[j]) continue;
if(temp>coins[j]) temp -=coins[j];
}
if(temp == 0) continue;
else return i;
}
}
官方参考代码
通过的代码要么和参考代码一样,要么就大同小异,我的评价是依托答辩
- 时间复杂度:时间复杂度:O(nlogn),其中 n 为数组 coins 的长度。主要为排序所需要的时间开销。
- 空间复杂度:O(logn)。排序需要 O(logn)的栈空间。
static int cmp(const void *pa, const void *pb) {
return *(int *)pa - *(int *)pb;
}
int getMaximumConsecutive(int* coins, int coinsSize) {
int res = 1;
qsort(coins, coinsSize, sizeof(int), cmp);
for (int i = 0; i < coinsSize; i++) {
if (coins[i] > res) {
break;
}
res += coins[i];
}
return res;
}