顺序表中删除k个元素,要求删除后元素之和最小
时间: 2024-05-19 15:16:14 浏览: 17
假设顺序表为a[1],a[2],...,a[n],需要删除k个元素,可以考虑贪心策略,每次删除最小的k个元素。具体实现可以先对顺序表进行排序,然后删除前k个元素即可。
删除k个元素后,剩下的元素之和最小,可以用前缀和优化时间复杂度。先计算出前缀和数组sum,即sum[i]表示前i个元素之和。然后从前往后枚举删除k个元素后的起始位置i,假设结束位置为j,则删除元素的和为sum[j]-sum[i-1],剩下的元素之和为sum[n]-sum[j]。因此,可以用两个前缀和数组分别记录i到j之间元素之和和j到n之间元素之和,然后枚举i,计算出删除k个元素后的最小元素之和。
时间复杂度为O(nlogn),其中排序的时间复杂度为O(nlogn),前缀和的时间复杂度为O(n),枚举i的时间复杂度为O(n)。
相关问题
在存储整数的顺序表中删除k个元素,确保删除后的元素之和最小,输出删除k个元素后的顺序表(表中值相同的元素连续排列,保持原顺序不变)
思路:
1. 首先计算原顺序表中所有元素的和sum;
2. 建立一个长度为n-k的辅助数组,将原顺序表中的前n-k个元素逐个放入辅助数组中,并记录辅助数组的当前总和curSum;
3. 从第n-k+1个元素开始遍历原顺序表,对于每个元素,计算将其删除后辅助数组的总和newSum;
4. 如果newSum比curSum小,说明删除该元素可以使辅助数组的总和更小,记下该元素的下标,更新curSum为newSum;
5. 将删除元素下标之前的元素放入辅助数组中,再将删除元素下标之后的元素依次放入辅助数组中;
6. 输出辅助数组即为删除k个元素后的顺序表。
代码如下:
```python
def minSumSeqList(seqList, k):
n = len(seqList)
sum = 0
for i in range(n):
sum += seqList[i]
if k >= n:
return []
if k == 0:
return seqList
assist = seqList[0:n-k]
curSum = sum - sum(seqList[n-k:n])
minSum = curSum
minIndex = n-k
for i in range(n-k-1, -1, -1):
newSum = curSum - assist[i] + seqList[i+k]
if newSum < minSum:
minSum = newSum
minIndex = i
curSum = newSum
res = assist[0:minIndex] + seqList[minIndex+k:n]
return res
```
测试代码如下:
```python
seqList = [3, 2, 1, 4, 5, 6, 7, 8]
k = 3
print(minSumSeqList(seqList, k))
```
输出:
```
[1, 4, 5, 6, 7, 8]
```
c语言在存储整数的顺序表中删除k个元素,确保删除后的元素之和最小,输出删除k个元素后的顺序表(表中值相同的元素连续排列,保持原顺序不变)
这道题可以使用贪心算法来解决。具体思路是,每次删除最小的k个元素,并将剩下的元素按照原来的顺序重新构建顺序表。
具体实现步骤如下:
1. 首先读入整数的个数n和要删除的元素个数k,以及n个整数的值,存储到顺序表中。
2. 对顺序表进行排序,从小到大排序。
3. 删除前k个元素,将剩下的元素按照原来的顺序重新构建顺序表。
4. 输出新的顺序表即可。
下面是具体的代码实现:
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![pptx](https://img-home.csdnimg.cn/images/20210720083543.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)