一、一个含有n个元素的数组，找出m个数使其和为K
参考：打印和为sum的组合，动规法+DFS+迭代法https://blog.csdn.net/qq_19446965/article/details/81775702
动态规划：只能找出一组，O(n^2)
找出所有参考上述；链接
// 打印和为n的组合，动规法，O(n^2)
public static List<Integer> findSums(int[] a, int n) {
boolean[] dp = new boolean[n + 1];
List<Integer>[] list = new ArrayList[101];
for (int i = 0; i < list.length; i++) {
list[i] = new ArrayList<>();
}
dp[a[0]] = true;
list[a[0]].add(a[0]);
for (int i = 1; i < a.length; i++) {
for (int j = n; j >= a[i]; j--) {
if (dp[j - a[i]]) {
dp[j] = true;
list[j].addAll(list[j - a[i]]);
list[j].add(a[i]);
}
}
if (dp[n]) {
break;
}
}
return list[n];
}
二、数据分组
题目描述
小组编号问题。输入一组数【2,7,3,4,9】，表示第一组有2个人，编号为【1、2】，第二组有7个人编号为【3~9】，第三组有3个人编号为【10~12】，第四组有4个人编号为【13~16】，第五组有9个人编号为【17~25】。
现在求，编号为1、25、11的人分别在哪个组里。
示例：
输入
5
2 7 3 4 9
3
1 25 11
输出
1 5 3
计算累加小组成员数，结合二分查找，复杂度O( min(n, mlogn) )
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int[] arr = new int[n];
arr[0] = sc.nextInt();
for (int i = 1; i < n; i++) {
arr[i] = arr[i - 1] + sc.nextInt();
}
int m = sc.nextInt();
int query = 0;
int index = 0;
for (int i = 0; i < m; i++) {
query = sc.nextInt();
index = search(arr, query);
System.out.print(index + " ");
}
}
sc.close();
}
public static int search(int a[], int target) {
int left = 0;
int right = a.length - 1;
int mid = 0;
while (left < right) {
mid = left + (right - left) / 2;
if (target >= a[mid]) {
left = ++mid;
} else {
right = mid;
}
}
return left + 1;
}
三、3个有序数组查找第k个
1. 在每一个数组中取出第一个值，然后把它们放在一个大小为3的小根堆中。此步骤的时间复杂度为O(3)
2. 取出堆中的最小值， 然后把该最小值所处的数组的下一个值放在数组的第一个位置。此步骤的时间复杂度为O(lg 3).
3. 不断的重复步骤二，直到去出k个或所有的数组都为空。
建堆只建一次，复杂度为O(3)；所以为O(3)+O(k*lg 3) = O(k)
public static int findKth(int[] a, int b[], int c[], int count) {
PriorityQueue<Integer> s = new PriorityQueue<>();
int i = 0, j = 0, k = 0;
s.add(a[i]);
s.add(b[j]);
s.add(c[k]);
while (count > 1) {
if (s.peek() == a[i]) {
s.poll();
if (i + 1 < a.length) {
s.add(a[++i]);
}
count--;
continue;
}
if (s.peek() == b[j]) {
s.poll();
if (j + 1 < b.length) {
s.add(b[++j]);
}
count--;
continue;
}
if (s.peek() == c[k]) {
s.poll();
if (k + 1 < c.length) {
s.add(c[++k]);
}
count--;
continue;
}
}
return s.peek();
}
| 
转播
