数组常见算法题

 

 

连续子数组的最大和

问题描述：

输入一个整型数组，数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和，求所有子数组和的最大值。

例如输入的数组为1,-2,3,10,-4,7,2,-5，和最大的子数组为3,10,-4,7,2，因此输出为该子数组的和18。

int max_sub(int a[], int size) {     int i;    int max=0;    int temp_sum=0;     for (i=0; i
     
      max) {               max = temp_sum;         }  else if (temp_sum<0) {            temp_sum = 0;          }       }       // if all data are negative    if (max == 0) {        max = a[0];        for (i=1; i
      
        max) max = a[i];         }       }       return max; }
      
     

 

 

---

 

数对之差的最大值

问题描述：

在数组中，数字减去它右边的数字得到一个数对之差，求所有数对之差的最大值。

例如在数组{2,4,1,16,7,5,11,9}中，数对之差的最大值是11，是16-5的结果。

这个问题用暴力法破解的话，时间复杂度是O(n^2)，我们可以换下思路。

构建一个辅助数组diff，并且diff[i]=number[i]-number[i+1] (0<=i<N-1)，那么 diff[i]+diff[i+1]+...+diff[j]=numbers[i]-number[j+1]，

可见最大的数对之差numbers[i]-number[j+1]，同时也是 diff[i]+diff[i+1]+...+diff[j]的最大值，也就是连续子数组的最大和，这就回到了上面那个问题了。

C代码实现如下：

#define N 8int main(){            int array[N] = {
   2,4,1,16,7,5,11,9};    int diff[N-1];    int j = 0;    for (; j

 

上面这种方法比较巧妙，一般不容易想到，我们再用一种比较常规的解法。

构建数组 diff[i] = max(number[h] - number[i])，（0<=h<i），现在问题就变成了求数组diff[i] (0<=i<N-1)的最大值。

假设我们已经知道了diff[i]，那么该怎么求diff[i+1]呢？对于diff[i]，肯定存在一个h（h<i），满足number[h]-number[i]最大，也就是number[h]应该是number[i]之前的所有数字的最大值。当我们求diff[i+1]的时候，需要找到第i+1个数字之前的最大值，这个值只有两种可能，一个是number[h]，另一个是number[i]。

C代码实现如下：

#define N 8#define MAX(a,b) (a>b?a:b)int main(){            int i;    int array[N] = {
   2,4,1,16,7,5,11,9};    int diff;    int last_max = array[0];    int max_diff = array[0] - array[1];    for (i=2; i
     
       max_diff)             max_diff = diff;    }        printf("the max sub is: %d\n", max_diff);  // 11    return 0;}
     

 

---

把数组排成最小的数

问题描述：

输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。

例如输入数组{32,321}，则输出这两个能排成的最小数字32132.

思路：

由于数组中的所有数字都是正整数，我们只要将它们的所有连接组合比较一下，找到最大值即可，但要考虑一个问题，就是很多数字连接起来可能会超出int表示范围，因此更好的做法就是将数字数组先转成字符串数组，然后对字符串数组排序（按字面值），再从头至尾依次连接所有字符串元素即可。

 

#define MAX_LEN 30int str_comp(const void *a, const void *b){    static char composite1[2*MAX_LEN+1];    static char composite2[2*MAX_LEN+1];    //memset(composite1, 0, 2*MAX_LEN+1);    //memset(composite2, 0, 2*MAX_LEN+1);    strcpy(composite1, (const char*)a);    strcat(composite1, (const char*)b);    strcpy(composite2, (const char*)b);    strcat(composite2, (const char*)a);    return strcmp(composite1, composite2);}void GetMinNumber(int a[], int N){    int n;    char strArray[N][MAX_LEN+1];    for (n=0; n

 

---

有序数组中和为给定值的两个数字

问题描述：

输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

思路：

由于数组已经有序，我们不妨先从数组的两端开始计算，用small指向第一个元素、用big指向最后一个元素，如果small+big恰好就是给定值m，那就找到了；如果(small+big)<m，就把small往后移动一次，如果(small+big)>m，就把big往后移动一次。

 

void FindTwoNum(int array[], int N, int m){    int *small = array;    int *big = array + N - 1;    while (small < big) {        if (*small + *big == m) {            printf("small=%d\tbig=%d\n", *small, *big);            break;        } else if (*small + *big < m) {            small++;        } else {            big--;        }       }   }int main(){    int a[6] = {
   1,2,4,7,11,15};    FindTwoNum(a, 6, 15);    return 0;}

 

问题扩展：

1、输入一个数组，判断这个数组中是不是存在三个数字i, j, k，满足i+j+k等于0。

2、如果输入的数组是没有排序的，但知道里面数字的范围，其他条件不变，如何在O(n)时间里找到这两个数字？

 

 

---

扑克牌的顺子

问题描述：

从扑克牌中随机抽5张牌，判断是不是一个顺子，即这5张牌是不是连续的。2-10为数字本身，A为1，J为11，Q为12，K为13，而大小王可以看成任意数字。

思路：

我们不妨把大小王都当成0，这样和其他扑克牌代表的数字就不重复了，也就是任意一张扑克牌的数字位于0-13之间。接下来我们来分析怎样判断5个数字是不是连续的：首先可以把数组排序。但值得注意的是，由于0可以当成任意数字，我们可以用0去补满数组中的空缺。也就是排序之后的数组不是连续的，即相邻的两个数字相隔若干个数字，但如果我们有足够的0可以补满这两个数字的空缺，这个数组实际上还是连续的。举个例子，数组排序之后为{0，1，3，4，5}。在1和3之间空缺了一个2，刚好我们有一个0，也就是我们可以它当成2去填补这个空缺。

于是我们需要做三件事情：把数组排序，统计数组中0的个数，统计排序之后的数组相邻数字之间的空缺总数。如果空缺的总数小于或者等于0的个数，那么这个数组就是连续的；反之则不连续。最后，我们还需要注意的是，如果数组中的非0数字重复出现，则该数组不是连续的。换成扑克牌的描述方式，就是如果一副牌里含有对子，则不可能是顺子。

 

C++代码实现如下：

bool IsContinuous(vector
     
       numbers, int maxNumber){    if(numbers.size() == 0 || maxNumber <=0)        return false;    // Sort the array numbers.    sort(numbers.begin(), numbers.end());    int numberOfZero = 0;    int numberOfGap = 0;    // how many 0s in the array?    vector
      
       ::iterator smallerNumber = numbers.begin();    for (; smallerNumber != numbers.end(); ++smallerNumber) {        if (*smallerNumber == 0) {            numberOfZero++;        } else {            break;        }       }       // get the total gaps between all adjacent two numbers    vector
       
        ::iterator biggerNumber = smallerNumber + 1;    while (biggerNumber < numbers.end()) {        // if any non-zero number appears more than once in the array,        // the array can't be continuous        if (*biggerNumber == *smallerNumber)            return false;        numberOfGap += *biggerNumber - *smallerNumber - 1;        smallerNumber = biggerNumber;        ++biggerNumber;    }       return (numberOfGap > numberOfZero) ? false : true;}int main(){    vector
        
          cards;    cards.push_back(3);    cards.push_back(0);    cards.push_back(4);    cards.push_back(1);    cards.push_back(5);    cout<< "result="<< IsContinuous(cards, 13)<
        
       
      
     

 

 

 

 

---

 

子数组换位问题

问题描述：

设a[0:n-1]是一个有n个元素的数组，k(0<=k<=n-1)是一个非负整数。 试设计一个算法将子数组a[0:k]与a[k+1,n-1]换位。

PS：要求算法在最坏情况下耗时O(n)，且只用到O(1)的辅助空间。

 

例如，数组 {a0, a1, a2, a3, a4, a5, a6, a7, a8, a9}，

1、若k=4（两个子数组等长），即需要将数组变成：{

a5, a6, a7, a8, a9, a0, a1, a2, a3, a4}，两个子数组的长度一样，直接两两交换a[i]与a[i+k]即可；

2、若k=1（后面的子数组更长），即需要将数组变成：{

a2, a3, a4, a5, a6, a7, a8, a9, a0, a1}，可以先把第一个子数组交换到整个数组的最后，得到：

{

a8, a9, a2, a3, a4, a5, a6, a7,  a0, a1}，然后对前面的子数组再交换一次，得到：

{

a2, a3, a4, a5, a6, a7, a8, a9,  a0, a1}

3、若k=6（前面的子数组更长），即需要将数组变成：{

a8, a9, a0, a1, a2, a3, a4, a5, a6, a7}，可以先把第二个子数组交换到整个数组的前面，得到：

{

a8, a9, a2, a3, a4, a5, a6, a7, a0, a1}，然后问题就变成了怎么把{a2, a3, a4, a5, a6, a7}与{a0, a1}交换了，递归处理即可。

 

//交换数组的两段大小相等的范围的对应数据//a[low1] <->a[low2]  a[low1+1]<->a[low2+1]  ... a[high1] <-> a[high2]void swap(int a[],int low1,int high1,int low2,int high2){    int temp;    while (low1 <= high1) {        temp = a[low1];        a[low1] = a[low2];        a[low2] = temp;        low1++;        low2++;    }   }//利用分治算法， 每次选择最小的数组进行换位void patition(int a[], int low, int k, int high){    if (low < high) {        if ((k-low+1) == (high-k)) {            swap(a,low,k,k+1,high);        } else if ((k-low+1)<(high-k)){            swap(a,low,k,low+high-k,high);            patition(a,low,k,low+high-k-1);        } else {            swap(a,low,high+low-k-1,k+1,high);            patition(a,high+low-k,k,high);        }       }   }//测试int main(){    int i;    int a[] = {
   0,1,2,3,4,5,6,7,8,9,10,11,12,13};    patition(a, 0, 4, 13);    for (i=0; i<14; i++) {        printf("%d  ",a[i]);    }    printf("\n");    return 0;}

 

---

 

求数组的主元素

问题描述：

大小为Ｎ的数组Ａ，其主元素是一个出现超过Ｎ／２次的元素（从而这样的元素最多有一个），怎么用线性时间算法得到一个数组的主元素（如果有的话）。

 

算法思想：

先将数组排序，如果数组的主元素存在，那么主元素一定位于数组中间位置，也就是说主元素一定是数组的中位数。那么问题就变成了怎么求中位数？

借鉴快排算法的思想，可以使用一个支点元素，将小于它的元素放在一边，大于它的元素放在另一边，然后看支点所在的位置k：

若k<N/2，那么中位数位于支点右边，递归处理右边的元素；

若k>N/2，那么中位数位于支点左边，递归处理左边的元素；

若k=N/2，则支点即中位数；

以上，根据快速排序的思想，可以在平均时间复杂度为O(lgn)的时间内找出一个数组的中位数，然后再用O(n)的时间检查它是否是主元素。

 

#include 
     
      #include 
      
       void swap(int *a, int *b) {    if (a != b) {        *a ^= *b;            *b ^= *a;            *a ^= *b;        }   }int Partition(int *array, int s, int e){    int n;    int m = s;    int pivot = array[e];    for (n=s; n
       
         N/2) {        GetMiddleElement(array, s, q-1, N);     } else {        GetMiddleElement(array, q+1, e, N);     }   }void GetMainElement(int *a, int N){    int n, count=0;    int m = GetMiddleElement(a, 0, N-1, N);     for (n=0; n
        
          N/2) {        printf("There is main element: %d\n", m);    } else {        printf("There is no main element");    }}int main(){    int a[15] = {
   4,4,3,3,4,11,9,4,4,2,4,5,4,9,4 };    GetMainElement(a, 15);}
        
       
      
     

 

另外一种思路：

若数组中主元素存在，且其个数为m，则有 m > N/2，两边同时减1，既有 m-1 > (N-2)/2。

也就是说在数组中随机找出两个元素e1、e2，如果e1 != e2，并且其中一个是主元素，则删除这两个元素，主元素在剩下的数组中仍是主元素。注意：如果e1、e2没有主元素，那么可能导致某个不是主元素的元素在剩下的数组中变成主元素。

int main(){     int i;    int pArr[6] = {
   4,4,4,4,6,6};      int arrLength = 6;  //数组长度      int element = pArr[0];      int value = 1;  //记录剪裁过程中遇到相同元素的个数      int delNum = 0; //记录裁剪数组的元素个数      int *dArr = (int *)malloc(arrLength * sizeof(int)); //记录被剪裁的数组元素      int dTop = 0; //当前剪裁数组的索引位置      for (i=1; i
     
       0) {   //如果当前数组相邻的元素不等，则需要裁剪得到新的数组                dArr[dTop++] = element;            dArr[dTop++] = pArr[i];            delNum += 2;              value--;            }        }        //如果裁剪之后出现了主元素，那么这个主元素有可能是个伪主元素      if (value > (arrLength - delNum)/2) {         for (i=0; i
      
        arrLength/2)            printf("主元素为:%d\n",element);        }        return 0;}
      
     

 

 

---

 

连续数打乱判断少了哪个数

问题描述：

N个连续的数（比如0～999）打乱 之后，随机取出1个数 ，问如何最快速的判断出少了哪一个？

算法描述：

由于数组顺序被打乱，最可行的办法就是建立一个bitmap，然后扫描一遍数组，并在bitmap中相应位置1，比如数组元素7就在bitmap第7位置1。最后再扫描一遍bitmap就知道缺失哪个数了，这样做的时间复杂度是O(2n)。

也可以用异或运算来分析下从0到N的异或结果，并将该结果与数组进行异或：

 

int main(){        int n;    int m = 34;    int N = 999;    int XOR = 0;    for (n=0; n

输出结果正是34，这是因为一个数和自身的异或结果是0，我们将0~(N-1)全部异或，再与数组所有元素异或，那么除了缺失的那个数字以外，其他所有元素都出现2次，因此这些数字最终都归为0。

异或算法的思路有点类似于将0~(N-1)相加，然后再减去数组所有元素之和，就刚好得到了缺失的那个数！

 

这个问题还可以进行一些拓展，比如：

1、一个连续数组，所有元素位于0~(N-1)之间，但有一个元素出现了2次，怎么快速找到多出来的这个数字？同样使用异或就可以搞定它！

2、一个连续数组，一个元素缺失，另一个元素重复了，怎么快速找到这两个数字？

3、在一个整型数组中，除了1个数字之外，其他的数字都出现了两次，怎么找到这1个只出现一次的数字？

4、在一个整型数组中，除了2个数字之外，其他的数字都出现了两次，怎么找到这2个只出现一次的数字？

5、在一个整型数组中，除了3个数字之外，其他的数字都出现了两次，怎么找到这3个只出现一次的数字？

 

以上面的第4个问题为例，假设数组中只出现一次的两个数字分别为a、b，且a != b，那么对数组所有元素进行异或，最后的结果x=a^b。由于a != b，故x != 0，其二进制表示中至少就有一位1，我们在x中找到第一个为1的位的位置，记为N位。现在以第N位是否为1将原数组中的数字分成两个子数组，那么a和b就分别位于这两个子数组中，然后分别对两个子数组进行异或，就能算到a、b的值了。代码如下：

#define N 10int main(){        int n, x, a, b, f;      a = b = x = n = f = 0;    int array[N] = {
   1,2,3,10,4,7,1,10,2,4};    for (n=0; n

 

再来看上面的第5题，有3个数字（设为a、b、c）仅出现一次，其它数字均出现了两次。如果我们能找到其中一个只出现一次的数字，那剩下2个数字就可以用问题4的解法来求了。

同样，对数组中所有数字进行异或，最后的结果x=a^b^c，由于a、b、c三个数字各不相等，那么x与a、b、c也都不想等。这点可以反证，如果x和a、b、c其中一个相等，比如x=a，那么a=a^b^c，两边同时异或a，那么有a^a=a^a^b^c，即b^c=0，与b!=c矛盾，可见x不会与a、b、c任意一个数字相等，也就是说x^a、x^b、x^c都不会等于0。

我们设置一个函数f(n)，可以只保留参数n的二进制中的最后一位1，比如f(6)=2、f(16)=16。接下来考虑f(x^a)^f(x^b)^ f(x^c)的结果，这个值肯定非0，假设最后一位是1的位是第m位，那么x^a、x^b、x^c的结果中，其中有且只有一个数字的第m位是1，我们可以把这个数字找到。然后剩下2个数字就可以用第4题的解法来求了。

 

 

---

 

一个数组先递增后递减，要求找到最大值

使用二分法：

int get_max(int a[], int N){    if (N <= 0) {        return -1;     } else if (N == 1) {        return a[0];    } else if (N == 2) {        return a[0] > a[1] ? a[0] : a[1];    }       int low = 0;    int high = N-1;    int mid = low + (high-low)/2;    while (mid>0 && mid
     
       a[mid+1] && a[mid] > a[mid-1]) {            return a[mid];        } else if (a[mid] < a[mid+1]) {            low = mid + 1;                        } else {            high = mid - 1;            }       }   }int main(){    int a[3] = {-3, 1, 10};    //int a[13] = {-3, -1, 0, 1, 5, 8, 11, 30, 29, 28, 27, -4, -100};    printf("max=%d\n", get_max(a, 3));}