顺序表sequeceList的扩展操作 ：
（1）数组中的最小元素，以及最小 的K个元素 ：
（2）数组中重复次数最多的元素 ：mostRepeated
（2.1）数组中出现次数超过一半的元素 ：
（2.2）出现次数刚好为一半的元素 ：
（3）数组A和数组B通过相同下标来构建名值对 key-value：
（4）数组的循环右移 rotate right/cycle shift right ：
（5）数组的反转reverse ：
（6）最大子序列和：maxSumSubarray :
（7）最长升序子数组： longestSortedSubarray：
（8）查找数组中和为定值value的两个元素 ：
（9） 两个数组的公共元素：
（分析：使用hash来实现）
--------------------------------------------------------------------------------------------------------
（1）数组中的最小元素，以及最小 的K个元素 ：
/*数组中最大值
初始时*maxValue=array[0];
*indexOfmax=0;
*/
void maxEle(elementType *array ,int length,elementType* maxValue,int* indexOfMax){
*maxValue=array[0];
*indexOfMax=0;
for(int i=1;i<length;i++){
if(array[i]>*maxValue){
*maxValue=array[i];
*indexOfMax=i;
}
}
}
求最小的k个元素：
（1.1）思路一：对n个元素进行升序排序，然后遍历前k个。
O（n^2）或者O(n*lgn) (后者是快速排序)
（1.2）思路二：利用选择排序中每次从后面的数组中选择出一个最小值。
所以，外层循环为i : 0~k-1；所以复杂度为O(k*n)
(1.3) 思路三：建立最大堆。
（1.4）思路四： 使用最小堆初始化这个数组，然后取优先队列的前k个数。
注意：求元素的最大值（最小值），步骤：
（1）一般需要创建两个变量。
1， maxValue 最大值
2. tempValue 临时值
（2）不断求得tempValue , 与 maxValue比较，更新maxValue;
如1：求数组中最大和子数组，需要创建maxSum,tempSum;
不断求得tempSum与maxSum比较，更新maxSum;
如2： 求得数组中的最大值，tempValue直接为数组中的元素,不需要求得。
如3： 有序数组中出现次数最多的 元素，
tmp_ele 对于 mostRepeatedEle;
tmp_count 对于 mostRepeatedCount;
（2）数组中重复次数最多的元素 ：mostRepeated ：
（1）先快速排序然后顺序遍历： O(n*lng+n);
（2）循环嵌套 ： O(n*n);
（3）hashTable: O(2*n);
（2.1）数组中出现次数超过一半的元素 ：
（1）思路一：先将数组快速排序，然后直接输出n/2处的元素即可。
分析：快速排序为O(n*lgn)，然后为什么n/2处是所找元素。
极限思想：如果所找的元素是最小的，则位于排序后数组的最前端，
超过n/2个，所以n/2处也是这个元素；
如果所找元素是最大的，同理。
（2）思路二： hash table, 时间复杂度为O(n),空间复杂度为O(n)
哈希表的键值（Key）为数组中的元素，值（Value）为该元素对应的次数。
直接遍历整个hash 表，找出每一个元素在对应的位置处出现的次数，输出那个
出现次数超过一半的元素即可。
（3）思路三 ：hash table ，时间复杂度为O(n),空间复杂度为O(1)。
如果每次删除两个不同的数（不管是不是我们要查找的那个
出现次数超过一半的数字），那么，在剩下的数中，我们要查找的数
（出现次数超过一半）出现的次数仍然超过剩余总数的一半。
（4）思路四：时间复杂度为O(n)，空间复杂度为O(1) 。
数组中某个元素出现的 次数超过了数组长度的一半，那么该元素出现的
次数比其他元素出现次数之和还要多。
在遍历数组的时候保存两个值：一个是数组中的一个数字，一个是次
数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保
存的数字相同，则次数加1。如果下一个数字和我们之前保存的数字不同，
则次数减1。如果次数为零，我们需要保存下一个数字，并把次数重新设为1。
实现如下 ：
Type Find(Type* a, int N) //a 代表数组，N 代表数组长度
{
Type candidate;
int nTimes, i;
// nTimes为元素出现的次数。
/*对于出现次数最多的元素，则每次与其他元素不同时，则nTimes--，
但是nTimes仍然大于0.
所以到最后candidate保存的就是出现次数最多的元素。
*/
for(i = nTimes = 0; i < N; i++)
{
if(nTimes == 0)
{
candidate = a[i], nTimes = 1;
}
else
{
if(candidate == a[i])
nTimes++;
else
nTimes--;
}
}
return candidate;
}
（2.2）出现次数刚好为一半的元素 ：
/*用两个临时变量来保存元素，两个nTimes来保存次数*/
int Find(int* a, int N)
{
int candidate1,candidate2;
int nTimes1, nTimes2, i;
for(i = nTimes1 = nTimes2 =0; i < N; i++)
{
if(nTimes1 == 0)
{
candidate1 = a[i], nTimes1 = 1;
}
else if(nTimes2 == 0 && candidate1 != a[i])
/*条件二是：第二个变量是否等于第一个*/
{
candidate2 = a[i], nTimes2 = 1;
}
else
{
if(candidate1 == a[i])
nTimes1++;
else if(candidate2 == a[i])
nTimes2++;
else
{
nTimes1--;
nTimes2--;
}
}
}
return nTimes1>nTimes2?candidate1:candidate2;
}
（3）数组A和数组B通过相同下标来构建名值对 key-value：
（4）数组的循环右移 rotate right/cycle shift right ：O(n)
如： 1,2,3,4 循环右移２位 得到 3,4 ,1,2
思路：循环右移m位，可以先将前n-m个元素reverse，然后将后m个元素reverse，然后整体reverse.
如1，2,3,4 循环右移得到3,4,1,2
1,2 reverse得到2，1；
3,4 reverse 得到4,3
2,1,4,3反转得到3,4,1,2
void rotate_right_n(eleType * array,int length,int n){
n=n%length;
reverse(array,0,length-n-1);
reverse(array,length-n,length-1);
reverse(array,0,length-1);
/*整体复杂度为O(n)
n为数组长度
*/
}
（5）数组的反转reverse ：O(n/2)
void reverse(int * array,int start,int end){
while(start<end){
swap(&array[start],&array[end]);
start++;
end--;
}
}
（6）最大子段和 ：maxSubsequenceSum :
（6.1）思路一：O(n)
elementType maxSubsequenceSum(elementType* array,int length){
elementType tmpSum=0,maxSum=0;
for(int i=0;i<length;i++){
tmpSum+=array[i];
if(tmpSum>maxSum){
maxSum=tmpSum;
}
else if(tmpSum<0){
tmpSum=0;
}
}
return maxSum;
}
/*不足：如果全是负数，则返回的是0，按理说应该返回的是
最大的那个负数。*/
改进：
将array[0]设置为数组中最大的数。
初始化时 maxSum=array[0];
（6.2）思路二：循环嵌套 ：O(n^2)
elementType maxSubsequenceSum(elementType* array,int length,int *startIndex,int* endIndex){
elementType tmpSum=0,maxSum=0;
*startIndex=0;
*endIndex=0;
for(int i=0;i<length;i++){
tmpSum=0;
for(int j=i;j<length;j++){
tmpSum+=array[j];
if(tmpSum>maxSum)
*startIndex=i;
*endIndex=j;
maxSum=tmpSum;
}
}
return maxSum;
}
/*思路二：可以求得最大子序列和，以及开始元素，结束元素；
*/
（6.3）思路三 ：动态规划 ：O(n)
（6.3.1）解析：
设b[i]表示以a[i]结尾 的子数组的最大子段和。
在计算b[i]时，可以考虑以下三种情况：
（1）b[i] = b[i-1]+a[i]，当b[i-1]>0时，这时候的b[i]中包含a[i]。
（ 注意：
此中不是根据a[i]的正负决定的，而是根据
b[i-1]的正负决定的，因为如果a[i]为负，然后a[i+1]是一个比a[i]
绝对值大的正数。则显然a[i],a[i+1]均是要加入的。
）
（2）b[i] = a[i]，当b[i-1]<=0，这时候以a[i]重新作为b[i]的起点。
（3）b[i]不包含a[i]的情况，这种情况在计算b[i]之前已经计算处结果，保存在b[0~i-1]中。
所以：b[i] = max{ b[i-1]+a[i]，a[i]}
（6.3.2）代码实现 ：
/*
函数返回最大子数组的和，以及起始位置，结束位置。
*/
elementType mostSumSubsequence(elementType* array,
int length ,int * start,int * end )
{
int tmpStart,tmpEnd;
elementType tmpSum,maxSum;
*end=*start=0;
tmpStart=tmpEnd=0;
/*
初始化均为0.
*end,*start的初始化与maxSum的初始化是对应的。
同时与tmpStart,tmpEnd,tmpSum也是对应的。
*/
tmpSum=maxSum=array[0];
for(int i=1;i<length;i++){
if(tmpSum>0){
tmpSum+=array[i];
tmpEnd=i;
/* a[i]>0
b[i]=b[i-1]+a[i];
同时更新end。
*/
}
else{
tmpSum=array[i];
tmpEnd=i;
tmpStart=i;
/*
b[i-1]<0
b[i]=a[i];
*/
}
if(maxSum<tmpSum){
maxSum=tmpSum;
*start=tmpStart;
*end=tmpEnd;
}
}
return maxSum;
}
（6.3.3）解析二以及代码实现二 ：
(1) 解析 ：
令cursum(i)表示数组下标以i为起点的最大连续下标最大的和，而maxsum(i)表示前i个元素的最大子数组之和。那么我们就可以推出下一个maxsum(i+1)应该为cursum(i+1)和maxsum(i)中选取一个最大值。递推式为：
cursum(i) = max{A[i],cursum(i-1)+A[i]};
maxsum(i) = max{maxsum(i-1),cursum(i+1)};
/*是否更新maxSum*/
（2）代码如上 ：
----------
（6.4）思路四 ： 分治法 O(n*lgn) ：（划分，解决，合并）
（6.4.1）分析 ：
把数组A[1..n]分成两个相等大小的块：A[1..n/2]和A[n/2+1..n]，最大的子数组只可能出现在三种情况：
1.在A[0..n/2]中、
2.在A[n/2+1,n-1]中、
3.跨过A[0..n/2]和A[n/2+1,n-1]、
（1）划分以及解决 ：
前两种情况的求法和整体的求法是一样的，因此递归求得。
第三种，我们可以采取的方法也比较简单，沿着第n/2向左搜索，直到左边界，找到最大的和maxleft，以及沿着第n/2+1向右搜索找到最大和maxright，那么总的最大和就是maxleft+maxright。
（2）合并：数组A的最大子数组和就是这三种情况中最大的一个。
（6.4.2）伪代码 ：
int maxSumSubArray(int *A,int l,int r) {
if l<r do
mid = (l+r)/2;
ml = maxSumSubArray(A,0,mid); //分治
mr = maxSumSubArray(A,mid+1,r);
for i=mid downto l do
search maxleft;
for i=mid+1 to r do
search maxright;
return max(ml,mr,maxleft+maxright); //归并
then //递归出口
return A[l];
}
（6.4.3）代码实现 ：
/*
输入：
arr : 输入的数组；
l，表示数组arr的左边界，
r，表示数组的右边界
输出 ：
left ，最大子数组的左边界 ；
right, 最大子数组的右边界；
返回值， 最大子数组的和；
*/
int max_sub_array(int arr[],int l,int r,int &left,int &right)
{
if(l<r){
int mid=(l+r)/2;
int ll,lr;
int suml=max_sub_array(arr,l,mid,ll,lr);
int rl,rr;
int sumr=max_sub_array(arr,mid+1,r,rl,rr);
int sum_both=0;
int max_left=-INF;
int ml,mr;
for(int i=mid;i>=l;i--)
{
sum_both+=arr[i];
if(sum_both>max_left){
max_left=sum_both;
ml=i;
}
}
int max_right=-INF;
sum_both=0;
for(int i=mid+1;i<=r;i++)
{
sum_both+=arr[i];
if(sum_both>max_right){
max_right=sum_both;
mr=i;
}
}
sum_both=max_left+max_right;
if(suml<sumr) {
if(sumr<sum_both) {
left=ml;
right=mr;
return sum_both;
}
else {
left=rl;
right=rr;
return sumr;
}
}
else{
if(suml<sum_both) {
left=ml;
right=mr;
return sum_both;
}
else {
left=ll;
right=lr;
return suml;
}
}
}
else {
left=l;
right=r;
return arr[l];
}
}
（7）最长升序子序列 longestSortedSubarray ： O(n)
/*
解析：动态规划思想；
设maxLen[i]为当前最长的升序子序列的长度，
if(a[i-1]<a[i])
tmpLen[i]++;
else tmpLen[i]=1;
maxLen[i]=max{maxLen[i-1],tmpLen[i]};
*/
int longestSortedSubarray(int* array,int length,int *start,int* end){
int tmpLen,longestLen;
int tmpStart,tmpEnd;
/*初始化*/
*start=0;
*end=0;
tmpStart=0;
tmpEnd=0;
tmpLen=1;
longestLen=1;
for(int i=1;i<length;i++){
if(array[i]>array[i-1])
{
tmpLen++;
tmpEnd=i;
}
else {
tmpLen=1;
tmpStart=i;
tmpEnd=i;
}
if(tmpLen>longestLen){
longestLen=tmpLen;
*start=tmpStart;
*end=tmpEnd;
}
}
return longestLen;
}
（8）查找数组中和为定值value的两个元素 ：
（8.1）思路一：对每个a[i]，查找sum-a[i]是否也在原始序列中，每一次要查找的时间
都要花费为O（N），这样下来，最终找到两个数还是需要O（N^2）的复杂度；
（8.2）思路二：二分查找:时间复杂度为O(n*lgn)
N 个a[i]，都要花logN 的时间去查找相对应的sum-a[i]是否在原始序列中，总的时间复杂度已降为O（N*logN），且空间复杂度为O（1）。
（如果有序，直接二分O（N*logN），如果无序，先排序后二分，复杂度同样为O
（N*logN+N*logN）=O（N*logN），空间总为O（1））。
（8.3）思路三 ：hashtable ：时间复杂度O(n)，空间复杂度O(n);
给定一个数字，根据hash映射查找另一个数字是否也在数组中，只需用O（1）的时间.
================================================
数组的扩展操作总结：
（1）数组的部分反转，总体反转：比如数组的循环右移；
（2）hash： 主要用于查找；
比如数组中出现次数最多的元素；
比如数组中和为sum的元素对；
比如两个数组中的公共元素；
比如两个数组中定制为value的两个元素；
（3）快排 || 选择排序：
比如数组中的top k的元素；
（4）最大最小堆；
数组中的 top k的元素；
（5）动态规划：
数组的最大子序列和及其子序列；
数组的最长升序子数组及其子数组；
（6）双指针：
比如：数组逆序；
数组是否对称；
快速排序；
二分查找；
标签：tmpSum,int,元素,扩展,maxSum,数组,array,legend From： https://blog.51cto.com/u_15911260/5934921