在存储整数的顺序表中删除k个元素,确保删除后的元素之和最小,输出删除k个元素后的顺序表(表中值相同的元素连续排列,保持原顺序不变)
时间: 2024-05-14 18:12:02 浏览: 16
思路:
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]
```