http://algorithmsforever.blogspot.com/2011/11/check-range.html
for(i=1; i<N; i++){
return (max - min + 1) == N;
}
http://www.cnblogs.com/graphics/archive/2010/08/24/1761620.html
给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：
// 字符串逆序
void Reverse(char*a, int n)
{
int left =0;
int right = n -1;
while (left < right)
{
char temp = a[left] ;
a[left++] = a[right] ;
a[right--] = temp ;
}
}
Write a function that takes an int array of size M, and returns (true/false) if the array consists of the numbers only within the range [N, N+M-1]. The array is not guaranteed to be sorted.
For instance, {2,3,4} would return true. {1,3,1} would return true, {1,2,4} would return false.
int check_range(int input[], int N){For instance, {2,3,4} would return true. {1,3,1} would return true, {1,2,4} would return false.
int max = input[0], min = input[0], i;
for(i=1; i<N; i++){
if(input[i] < min) min=input[i];
if(input[i] > max) max=input[i];
}if(input[i] > max) max=input[i];
return (max - min + 1) == N;
http://www.cnblogs.com/graphics/archive/2010/08/24/1761620.html
给定含有n个元素的整型数组a，其中包括0元素和非0元素，对数组进行排序，要求：
1. 排序后所有0元素在前，所有非零元素在后，且非零元素排序前后相对位置不变
2. 不能使用额外存储空间
例子如下
输入 0, 3, 0, 2, 1, 0, 0
输出 0, 0, 0, 0, 3, 2, 1
void Arrange(int* a, int n) { int k = n -1 ; for (int i = n -1; i >=0; --i) { if (a[i] !=0) { if (a[k] ==0) { a[k] = a[i] ; a[i] =0 ; } --k ; } } }
给定一个有序整数序列（非递减序），可能包含负数，找出其中绝对值最小的元素，比如给定序列 -5, -3, -1, 2, 8 则返回1。
由于给定序列是有序的，而这又是搜索问题，所以首先想到二分搜索法，只不过这个二分法比普通的二分法稍微麻烦点，可以分为下面几种情况
- 如果给定的序列中所有的数都是正数，那么数组的第一个元素即是结果。
- 如果给定的序列中所有的数都是负数，那么数组的最后一个元素即是结果。
- 如果给定的序列中既有正数又有负数，那么绝对值得最小值一定出现在正数和负数的连接处。
为什么？因为对于负数序列来说，右侧的数字比左侧的数字绝对值小，如上面的-5, -3, -1, 而对于整整数来说，左边的数字绝对值小，比如上面的2, 8，将这个思想用于二分搜索，可先判断中间元素和两侧元素的符号，然后根据符号决定搜索区间，逐步缩小搜索区间，直到只剩下两个元素。
// 找出一个非递减序整数序列中绝对值最小的数 int MinimumAbsoluteValue(int* a, int n) { // Only one number in array if (n ==1) { return a[0] ; } // All numbers in array have the same sign if (SameSign(a[0], a[n -1])) { return a[0] >=0? a[0] : a[n -1] ; } // Binary search int l =0 ; int r = n -1 ; while(l < r) { if (l + 1 == r) { return abs(a[l]) < abs(a[r]) ? a[l] : a[r] ; } int m = (l + r) /2 ; if (SameSign(a[m], a[r])) { r = m; continue; } else { l = m ; continue; } } }
// 合并两个有序数组 void Merge(int *a, int *b, int *c, int n) { int i = 0 ; int j = 0 ; int k = 0 ; while (i < n && j < n) { if (a[i] < b[j])// 如果a的元素小，则插入a中元素到c { c[k++] = a[i] ; ++i ; } else if (a[i] == b[j])// 如果a和b元素相等，则插入二者皆可，这里插入a { c[k++] = a[i] ; ++i ; ++j ; } else // a[i] > b[j] // 如果b中元素小，则插入b中元素到c { c[k++] = b[j] ; ++j ; } } if (i == n) // 若a遍历完毕，处理b中剩下的元素 { for (int m = j; m < n; ++m) c[k++] = b[m] ; } else//j == n, 若b遍历完毕，处理a中剩下的元素 { for (int m = i; m < n; ++m) c[k++] = a[m] ; } }
给定一个含有n个元素的整型数组a，从中任取m个元素，求所有组合。比如下面的例子
a = 1, 2, 3, 4, 5
m = 3
输出
1 2 3, 1 2 4, 1 2 5, 1 3 4, 1 3 5, 1 4 5
2 3 4, 2 3 5, 2 4 5
3 4 5
3 4 5
bool IsValid(int lastIndex, int value) { for (int i = 0; i < lastIndex; i++) { if (buffer[i] >= value) return false; } return true; } void Select(int t, int n, int m) { if (t == m) PrintArray(buffer, m); else { for (int i = 1; i <= n; i++) { buffer[t] = i; if (IsValid(t, i)) Select(t + 1, n, m); } } }
// 字符串逆序
void Reverse(char*a, int n)
{
int left =0;
int right = n -1;
while (left < right)
{
char temp = a[left] ;
a[left++] = a[right] ;
a[right--] = temp ;
}
}
// 子数组的最大乘积 int MaxProduct(int *a, int n) { int maxProduct = 1; // max positive product at current position int minProduct = 1; // min negative product at current position int r = 1; // result, max multiplication totally for (int i = 0; i < n; i++) { if (a[i] > 0) { maxProduct *= a[i]; minProduct = min(minProduct * a[i], 1); } else if (a[i] == 0) { maxProduct = 1; minProduct = 1; } else // a[i] < 0 { int temp = maxProduct; maxProduct = max(minProduct * a[i], 1); minProduct = temp * a[i]; } r = max(r, maxProduct); } return r; }
常规的做法是遍历一次，分别求出最大值和最小值，但我这里要说的是分治法(Divide and couquer)，将数组分成左右两部分，先求出左半部份的最大值和最小值，再求出右半部份的最大值和最小值，然后综合起来求总体的最大值及最小值。这是个递归过程，对于划分后的左右两部分，同样重复这个过程，直到划分区间内只剩一个元素或者两个元素。
// 求数组的最大值和最小值，返回值在maxValue和minValue void MaxandMin(int *a, int l, int r, int& maxValue, int& minValue) { if(l == r) // l与r之间只有一个元素 { maxValue = a[l] ; minValue = a[l] ; return ; } if(l + 1 == r) // l与r之间只有两个元素 { if(a[l] >= a[r]) { maxValue = a[l] ; minValue = a[r] ; } else { maxValue = a[r] ; minValue = a[l] ; } return ; } int m = (l + r) / 2 ; // 求中点 int lmax ; // 左半部份最大值 int lmin ; // 左半部份最小值 MaxandMin(a, l, m, lmax, lmin) ; // 递归计算左半部份 int rmax ; // 右半部份最大值 int rmin ; // 右半部份最小值 MaxandMin(a, m + 1, r, rmax, rmin) ; // 递归计算右半部份 maxValue = max(lmax, rmax) ; // 总的最大值 minValue = min(lmin, rmin) ; // 总的最小值 }
思想和上一题类似，同样是用分治法，先求出左边的最大值leftmax和次大值leftsecond，再求出右边的最大值rightmax和次大值rightsecond，然后合并，如何合并呢？分情况考虑
1 如果leftmax > rightmax，那么可以肯定leftmax是最大值，但次大值不一定是rightmax，但肯定不是rightsecond，只需将leftsecond与rightmax做一次比较即可。
2 如果rightmax > leftmax，那么可以肯定rightmax是最大值，但次大值不一定是leftmax，但肯定不是leftsecond，所以只需将leftmax与rightsecond做一次比较即可。
这种方法无法处理最大元素有多个的情况，比如3,5,7,7将返回7，7而不是7,5// 找出数组的最大值和次大值，a是待查找的数组，left和right是查找区间，max和second存放结果 void MaxandMin(int a[], int left, int right, int&max, int&second) { if(left == right) { max = a[left] ; second = INT_MIN; } elseif(left +1== right) { max = a[left] > a[right] ? a[left] : a[right] ; second = a[left] < a[right] ? a[left] : a[right] ; } else { int mid = left + (right - left) /2 ; int leftmax ; int leftsecond ; MaxandMin(a, left, mid, leftmax, leftsecond) ; int rightmax ; int rightsecond ; MaxandMin(a, mid +1, right, rightmax, rightsecond) ; if (leftmax > rightmax) { max = leftmax ; second = leftsecond > rightmax ? leftsecond : rightmax ; } else { max = rightmax ; second = leftmax < rightsecond ? rightsecond : leftmax ; } } }
