输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
示例 1:
输入:arr = [3,2,1], k = 2 输出:[1,2] 或者 [2,1]
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if (k == 0) {
return new int[0];
}
Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
public int compare(Integer a, Integer b) {
return b - a;
}
});
for (int i : arr) {
if (queue.isEmpty() || queue.size() < k || i < queue.peek()) {
queue.offer(i);
}
if (queue.size() > k) {
queue.poll();
}
}
int[] ans = new int[k];
int start = 0;
for (int i : queue) {
ans[start++] = i;
}
return ans;
}
}
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0;
int ans = nums[0];
for (int i : nums) {
pre = Math.max(i, pre + i);
ans = Math.max(pre, ans);
}
return ans;
}
}