数组的一些常见操作汇总
数组的一些常见操作汇总

转自http://www.nowamagic.net/datastructures/ds_SumaryOfArrayControl.php

数组是最基本的数据结构，关于数组的操作是程序员最经常用到的。这里将一些常用的操作写成函数。
数组求和

给定一个含有n个元素的整型数组a，求a中所有元素的和。可能您会觉得很简单，是的，的确简单，但是为什么还要说呢，原因有二，第一，这道题要求用递归法，只用一行代码。第二，这是我人生中第一次面试时候遇到的题，意义特殊。

简单说一下，两种情况：

如果数组元素个数为0，那么和为0。
如果数组元素个数为n，那么先求出前n - 1个元素之和，再加上a[n - 1]即可。

如果三个数组都无序，可以先对a, b进行排序，然后对c中任意一个元素都在b和c中做二分搜索。


最大子段和

给定一个整型数组a，求出最大连续子段之和，如果和为负数，则按0计算，比如1， 2， -5， 6， 8则输出6 + 8 = 14。

编程珠玑上的经典题目，不多说了。


合并两个数组

给定含有n个元素的两个有序（非降序）整型数组a和b。合并两个数组中的元素到整型数组c，要求去除重复元素并保持c有序（非降序）。例子如下：

a = 1, 2, 4, 8
b = 1, 3, 5, 8
c = 1, 2, 3, 4, 5, 8

利用合并排序的思想，两个指针i,j和k分别指向数组a和b，然后比较两个指针对应元素的大小，有以下三种情况：

    a[i] < b[j]，则c[k] = a[i]。
    a[i] == b[j]，则c[k]等于a[i]或b[j]皆可。
    a[i] > b[j]，则c[k] = b[j]。

重复以上过程，直到i或者j到达数组末尾，然后将剩下的元素直接copy到数组c中即可。
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 ;        }    }}