全部博文(164)
分类: C/C++
2012-04-20 15:54:47
分析:
咱们试着一步一步解决这个问题(注意阐述中数列有序无序的区别):
总结:
代码:
ok,在进入第二节之前,咱们先来实现思路5(这里假定数组已经是有序的),代码可以如下编写(两段代码实现)://代码一
//O(N)
Pair findSum(int *s,int n,int x)
{
//sort(s,s+n); 如果数组非有序的,那就事先排好序O(N*logN)
int *begin=s;
int *end=s+n-1;
while(begin
扩展:
1、如果在返回找到的两个数的同时,还要求你返回这两个数的位置列?
2、如果把题目中的要你寻找的两个数改为“多个数”,或任意个数列?(请看下面第二节)
3、二分查找时: left <= right,right = middle - 1;left < right,right = middle;
//算法所操作的区间,是左闭右开区间,还是左闭右闭区间,这个区间,需要在循环初始化,
//循环体是否终止的判断中,以及每次修改left,right区间值这三个地方保持一致,否则就可能出错.//二分查找实现一
int search(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n - 1;
while (left <= right)
{
middle = left + (right-left)/2;
if (array[middle] > v)
{
right = middle - 1;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}//二分查找实现二
int search(int array[], int n, int v)
{
int left, right, middle;
left = 0, right = n;
while (left < right)
{
middle = left + (right-left)/2;
if (array[middle] > v)
{
right = middle;
}
else if (array[middle] < v)
{
left = middle + 1;
}
else
{
return middle;
}
}
return -1;
}
第二节、寻找满足条件的多个数
第21题(数组)
2010年中兴面试题
编程求解:
输入两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来。
解法一
我想,稍后给出的程序已经足够清楚了,就是要注意到放n,和不放n个区别,即可,代码如下:
// 21题递归方法
//copyright@ July && yansha
//July、yansha,updated。
#include
#include
解法二
@zhouzhenren:
这个问题属于子集和问题(也是背包问题)。本程序采用 回溯法+剪枝
X数组是解向量,t=∑(1,..,k-1)Wi*Xi, r=∑(k,..,n)Wi
若t+Wk+W(k+1)<=M,则Xk=true,递归左儿子(X1,X2,..,X(k-1),1);否则剪枝;
若t+r-Wk>=M && t+W(k+1)<=M,则置Xk=0,递归右儿子(X1,X2,..,X(k-1),0);否则剪枝;
本题中W数组就是(1,2,..,n),所以直接用k代替WK值。
代码编写如下:
//copyright@ 2011 zhouzhenren
//输入两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数,
//使其和等于 m ,要求将其中所有的可能组合列出来。
#include
扩展:
1、从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的(网易)。
2、有两个序列a,b,大小都为n,序列元素的值任意整数,无序;
要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];(微软100题第32题)。
@well:[fairywell]:
给出扩展问题 1 的一个解法:
1、从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的(网易)。
双端 LIS 问题,用 DP 的思想可解,目标规划函数 max{ b[i] + c[i] - 1 }, 其中 b[i] 为从左到右, 0 ~ i 个数之间满足递增的数字个数; c[i] 为从右到左, n-1 ~ i 个数之间满足递增的数字个数。最后结果为 n - max + 1。其中 DP 的时候,可以维护一个 inc[] 数组表示递增数字序列,inc[i] 为从小到大第 i 大的数字,然后在计算 b[i] c[i] 的时候使用二分查找在 inc[] 中找出区间 inc[0] ~ inc[i-1] 中小于 a[i] 的元素个数(low)。
源代码如下:
/** * The problem: * 从一列数中筛除尽可能少的数使得从左往右看,这些数是从小到大再从大到小的(网易)。 * use binary search, perhaps you should compile it with -std=c99 * fairywell 2011 */ #include#define MAX_NUM (1U<<31) int main() { int i, n, low, high, mid, max; printf("Input how many numbers there are: "); scanf("%d/n", &n); /* a[] holds the numbers, b[i] holds the number of increasing numbers * from a[0] to a[i], c[i] holds the number of increasing numbers * from a[n-1] to a[i] * inc[] holds the increasing numbers * VLA needs c99 features, compile with -stc=c99 */ double a[n], b[n], c[n], inc[n]; printf("Please input the numbers:/n"); for (i = 0; i < n; ++i) scanf("%lf", &a[i]); // update array b from left to right for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM; //b[0] = 0; for (i = 0; i < n; ++i) { low = 0; high = i; while (low < high) { mid = low + (high-low)*0.5; if (inc[mid] < a[i]) low = mid + 1; else high = mid; } b[i] = low + 1; inc[low] = a[i]; } // update array c from right to left for (i = 0; i < n; ++i) inc[i] = (unsigned) MAX_NUM; //c[0] = 0; for (i = n-1; i >= 0; --i) { low = 0; high = i; while (low < high) { mid = low + (high-low)*0.5; if (inc[mid] < a[i]) low = mid + 1; else high = mid; } c[i] = low + 1; inc[low] = a[i]; } max = 0; for (i = 0; i < n; ++i ) if (b[i]+c[i] > max) max = b[i] + c[i]; printf("%d number(s) should be erased at least./n", n+1-max); return 0; } @yansha:fairywell的程序很赞,时间复杂度O(nlogn),这也是我能想到的时间复杂度最优值了。不知能不能达到O(n)。
扩展题第2题
当前数组a和数组b的和之差为
A = sum(a) - sum(b)a的第i个元素和b的第j个元素交换后,a和b的和之差为
A' = sum(a) - a[i] + b[j] - (sum(b) - b[j] + a[i])
= sum(a) - sum(b) - 2 (a[i] - b[j])
= A - 2 (a[i] - b[j])设x = a[i] - b[j],得
|A| - |A'| = |A| - |A-2x|假设A > 0,
当x 在 (0,A)之间时,做这样的交换才能使得交换后的a和b的和之差变小,x越接近A/2效果越好,
如果找不到在(0,A)之间的x,则当前的a和b就是答案。所以算法大概如下:
在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j,交换相应的i和j元素,重新计算A后,重复前面的步骤直至找不到(0,A)之间的x为止。接上,@yuan:
a[i]-b[j]要接近A/2,则可以这样想,
我们可以对于a数组的任意一个a[k],在数组b中找出与a[k]-C最接近的数(C就是常数,也就是0.5*A)
这个数要么就是a[k]-C,要么就是比他稍大,要么比他稍小,所以可以要二分查找。查找最后一个小于等于a[k]-C的数和第一个大于等于a[k]-C的数,
然后看哪一个与a[k]-C更加接近,所以T(n) = nlogn。
本章完。