给定n 个不同数的数组 S 和正整数 i,i<n^(1/2),求 S 中最大的i个数,并且按照从大到小的次序输出.有下述算法: 算法 A:调用i次找最大算法 Findmax,每次从 S 中删除一个最大的数。算法 B:对 S 排序,并输出 S 中最大的i个数. (1) 分析 A,B 两个算法在最坏情况下的时间复杂度 (2)试设计一个最坏情况下时间复杂度的阶更低的算法,要求给出伪码
时间: 2023-04-05 22:00:22 浏览: 276
(1) A算法的最坏情况下时间复杂度为O(n*i),B算法的最坏情况下时间复杂度为O(n*logn)。
(2) 可以使用堆排序来实现,最坏情况下时间复杂度为O(n*logi)。具体伪码如下:
1. 建立一个大小为i的小根堆,将S中前i个数插入堆中。
2. 遍历S中剩余的数,对于每个数,如果它比堆顶元素大,则将堆顶元素弹出,将该数插入堆中。
3. 遍历完S后,堆中的元素即为S中最大的i个数,按照从大到小的次序输出即可。
相关问题
用java完成给定一组正整数数组M,找出M数组中N项和为给定数S
可以使用回溯算法来解决这个问题。具体步骤如下:
1. 定义一个方法 backtrack(int[] nums, int target, int start, List<Integer> path, List<List<Integer>> res),其中 nums 表示输入的正整数数组,target 表示目标和,start 表示从哪个位置开始搜索,path 表示当前的路径,res 表示最终的结果集。
2. 在 backtrack 方法中,首先判断当前的路径是否满足条件,如果满足,则将其加入结果集中。
3. 然后从 start 开始遍历数组,对于每个数,将其加入当前路径中,更新目标和,然后递归调用 backtrack 方法。
4. 在递归调用完成后,需要将当前数从路径中删除,同时将目标和恢复到之前的状态。
下面是 Java 代码实现:
```
public List<List<Integer>> findNsum(int[] nums, int target, int start, int N) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
if (N < 2 || len < N) return res;
if (N == 2) {
int left = start, right = len - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
List<Integer> path = new ArrayList<>();
path.add(nums[left]);
path.add(nums[right]);
res.add(path);
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
} else {
for (int i = start; i < len - N + 1; i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
List<List<Integer>> sub = findNsum(nums, target - nums[i], i + 1, N - 1);
for (List<Integer> path : sub) {
path.add(0, nums[i]);
res.add(path);
}
}
}
return res;
}
```
其中,findNsum 方法中的参数分别表示:nums 表示输入的正整数数组,target 表示目标和,start 表示从哪个位置开始搜索,N 表示要找的数字个数。在方法中,首先判断 N 的值,如果是 2,就使用双指针法查找满足条件的两个数;否则,就递归调用 findNsum 方法,在子问题中查找 N-1 个数的和为 target-nums[i] 的路径,并将 nums[i] 加入路径中,最后将路径加入结果集中。
给定一组正整数数组M,找出M数组中N项和为给定数S。如果有多对N项数字的和都等于 S,则输出N个数的乘积最小的哪一项,没有则返回空;
这道题可以用双指针来解决。先将M数组排序,然后使用双指针i和j,i指向M数组的第一项,j指向M数组的最后一项。如果i和j指向的两个数的和大于S,则将j向左移动一位;如果i和j指向的两个数的和小于S,则将i向右移动一位;如果i和j指向的两个数的和等于S,则找到了一组解。
为了找到乘积最小的那一组解,我们可以使用一个变量minProduct来记录当前乘积最小的一组解。每当找到一组和为S的解时,我们就计算它们的乘积并与minProduct比较,如果小于minProduct则更新minProduct。最后返回minProduct即可。
以下是JavaScript的实现代码:
```
function findMinProduct(M, S, N) {
M.sort((a, b) => a - b); // 排序
let i = 0, j = M.length - 1, minProduct = Infinity;
while (i < j) {
if (M[i] + M[j] === S) {
if (N === 2) {
minProduct = Math.min(minProduct, M[i] * M[j]);
i++;
j--;
} else {
// 递归查找剩余的N-2个数
let subMinProduct = findMinProduct(M.slice(i + 1, j), S - M[i] - M[j], N - 2);
if (subMinProduct !== Infinity) {
minProduct = Math.min(minProduct, M[i] * M[j] * subMinProduct);
}
i++;
}
} else if (M[i] + M[j] < S) {
i++;
} else {
j--;
}
}
return minProduct === Infinity ? null : minProduct;
}
```
其中,M是正整数数组,S是目标和,N是要求的项数。如果找到了一组解,则返回它们的乘积;否则返回null。