数组

1.二维数组中的查找
在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
class Solution {
public:
    bool Find(vector<vector<int> > array,int target) {
        int m,n,x,y;
        m = array.size();//行数
        n = array[0].size();//列数
        x=m-1;y=0;//坐标定在左下角
        while(x>=0 && y<=n-1){
          if(target<array[x][y]){
                       x--;//遇小上移
                 }
          else if(target>array[x][y]){
                       y++;//遇大右移
                 }
          else {
               return true;
             }
      }
       return false;
    }
};
2.像素翻转
有一副由NxN矩阵表示的图像，这里每个像素用一个int表示，请编写一个算法，在不占用额外内存空间的情况下(即不使用缓存矩阵)，将图像顺时针旋转90度。
给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于500，图像元素小于等于256。
class Transform {
public:
    vector<vector<int> > transformImage(vector<vector<int> > mat, int n) {
        // write code here
        int i,j,temp=0;
    for (i=0;i<n;i++)
    {
        for (j=0;j<n/2;j++)
        {
            temp=mat[i][j];
            mat[i][j]=mat[i][n-1-j];
            mat[i][n-1-j]=temp;
        }
    }
    for (i=0;i<n;i++)
    {
        for (j=0;j<n-i;j++)
        {
            temp=mat[i][j];
            mat[i][j]=mat[n-1-j][n-1-i];
            mat[n-1-j][n-1-i]=temp;
        }
    }
    return mat;
    }
};




3.清除行列
请编写一个算法，若MxN矩阵中某个元素为0，则将其所在的行与列清零。
给定一个MxN的int[][]矩阵(C++中为vector<vector>)mat和矩阵的阶数n，请返回完成操作后的int[][]矩阵(C++中为vector<vector>)，保证n小于等于300，矩阵中的元素为int范围内。
class Clearer {
public:
    vector<vector<int> > clearZero(vector<vector<int> > mat, int n) {
        // write code here
  if(mat.empty())
   return vector<vector<int> >();
  int len1=mat.size();//行数
  int len2=mat[0].size();//列数
  bool *sign1=new bool[len1]();
  bool *sign2=new bool[len2]();
  for(int i=0;i<len1;i++)
   for(int j=0;j<len2;j++)
    if(mat[i][j]==0)
    {
     sign1[i]=true;
     sign2[j]=true;
    }
  for(int i=0;i<len1;i++)
   for(int j=0;j<len2;j++)
    if(sign1[i]||sign2[j])
     mat[i][j]=0;
  return mat;
    }
};




4.蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形。




样例输入
5
样例输出
1 3 6 10 15
2 5 9 14
4 8 13
7 12
11








#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    while(cin>>n)
    {
        vector< vector<int >> vec;
        for(int i=0;i<n;i++)
        {
            vector<int> tmp(n-i,0);
            vec.push_back(tmp);
        }
 
        for(int i=0;i<n;i++)
        {
            int cnt=i+1;
            for(int row=i, j=0;(j<cnt && row>=0);j++,row--)
            {
                vec[row][j]=(i+1)*i/2+1+j;
            }
        }
 
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<vec[i].size()-1;j++)
                cout<<vec[i][j]<<" ";
            cout<<vec[i][vec[i].size()-1]<<endl;
        }      
 
    }
 
}








5.数组中只出现一次的数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。




思路就是使用异或，但是与在成对出现的数字中查找一个单独的数字不同的是需要利用异或结果的最低位为1的flag将数组中的数字分为两类，一类是与flag按位与为0，另一类为不为0，这样再分别异或一次就能够找出这两个数。很是巧妙。其中有一个语法上容易忽略的坑：==的优先级比&高，所以&时需要加括号。




classSolution {
public:
    voidFindNumsAppearOnce(vector<int> data,int* num1,int*num2) {
        if(data.size() < 2) return;
        intmyxor = 0;
        intflag = 1;
        for(inti = 0 ; i < data.size(); ++ i )
            myxor ^= data[i];
        while((myxor & flag) == 0) flag <<= 1;
        *num1 = myxor;
        *num2 = myxor;
        for(inti = 0; i < data.size(); ++ i ){
            if((flag & data[i]) == 0) *num2 ^= data[i];
            else*num1 ^= data[i];
        }
    }
};


6.和为S的连续正数序列
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答
案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包
括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问
题交给你,你能不能也很快的找出所有和为S的连续正数序列? 
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
        if(sum<3)
            return res;
        int begin = 1;
        int end = 2;
        //初始化curSum时直接用3，不要用a+b,这样效率会高一点
        int curSum = 3;
        int mid = (1+sum)>>1;
        //当begin<mid或者end<(mid+1)时，连续序列的和肯定超出sum了，所以这两个都要限制一下
        while(begin<mid && end<mid+1){
            while(curSum>sum){
                curSum -= begin;
                ++begin;
            }
            //这段代码不要上一个while之前，不然会代码重复，而且多了一次判断，效率不高
            if(curSum==sum)
                insertRes(begin,end,res);
            ++end;
            curSum += end;
        }
        return res;
    }
private:
    void insertRes(int a,int b,vector<vector<int>> &res){  vector<int> temp;
        for(int i=a;i<=b;++i)
            temp.push_back(i);
        res.push_back(temp);  }
};




7.和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，
如果有多对数字的和等于S，输出两个数的乘积最小的。 
输出描述:
对应每个测试案例，输出两个数，小的先输出。
class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> v;
        if(array.empty())
            return v;
        int n=array.size();
        int i=0,j=n-1;
        while(i<=j){
            if(array[i]+array[j]==sum){
                v.push_back(array[i]);
                v.push_back(array[j]);
                break;
            }
            else if(array[i]+array[j]>sum) j--;
                 else i++;
        }
        return v;     
    }
};
8.元素查找
有一个排过序的数组，包含n个整数，但是这个数组向左进行了一定长度的移位，例如，原数组为[1,2,3,4,5,6]，向左移位5个位置即变成了[6,1,2,3,4,5],现在对于移位后的数组，需要查找某个元素的位置。请设计一个复杂度为log级别的算法完成这个任务。
给定一个int数组A，为移位后的数组，同时给定数组大小n和需要查找的元素的值x，请返回x的位置(位置从零开始)。保证数组中元素互异。
测试样例：
[6,1,2,3,4,5],6,6
返回：0
class Finder {
public:
   int findElement(vector<int> A, int n, int x) {
        int i=0,j=n-1,mid;
        while(i<=j) {
            mid=(i+j)/2;
            if(A[mid]==x)
                return mid;
            if(A[mid]<x) {
                if(A[mid]<A[i]&&x>A[j]) j=mid-1;
                else i=mid+1;
            }
            else {
                if(A[mid]>A[i]&&x<A[i]) i=mid+1;
                else j=mid-1;
            }
        }
        return -1;
}
};


9.数组中的逆序对
有一组数，对于其中任意两个数组，若前面一个大于后面一个数字，则这两个数字组成一个逆序对。请设计一个高效的算法，计算给定数组中的逆序对个数。
给定一个int数组A和它的大小n，请返回A中的逆序对个数。保证n小于等于5000。
测试样例：
[1,2,3,4,5,6,7,0],8
返回：7
class AntiOrder {
public:
    int count(vector<int> A, int n) {
        // write code here
        int count = 0;
        int i,j;
        if(n < 2) return n;
        for(i=0;i<n;i++){
            for(j=0;j<n-i-1;j++){
                if(A[j]>A[j+1]){
                    swap(A[j],A[j+1]);
                    count++;
                }
            }
        }
        return count;
    }
};
10.最小调整有序
有一个整数数组，请编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。注意：n-m应该越小越好，也就是说，找出符合条件的最短序列。
给定一个int数组A和数组的大小n，请返回一个二元组，代表所求序列的起点和终点。(原序列位置从0开始标号,若原序列有序，返回[0,0])。保证A中元素均为正整数。
测试样例：
[1,4,6,5,9,10],6
返回：[2,3]
class Rearrange {
public:
    vector<int> findSegment(vector<int> A, int n) {
        // write code here
        int left=n,right=-1;
        vector<int> vNum(2,0);
        int i,j;
        for(i=1;i<n;i++){
            for(j=0;j<i;j++){
                if(A[i]<A[j]){
                    if(left>j)
                        left = j;
                    if(right<i)
                        right = i;
                }
            }
        }
        if(left<=right){
            vNum[0] = left;
            vNum[1] = right;
        }
        return vNum;
    }
};
11.数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if(data.size()==0)
            return 0;
        int low=0,high=data.size()-1;
        int index = -1;
        while(low<=high){
            int mid = (low+high)>>1;
            if(data[mid]==k){
                index = mid;
                break;
            }
            else if(data[mid]>k)
                high = mid-1;
            else
                low = mid+1;
        }
        if(index==-1)
            return 0;
        low = index-1;
        high = index+1;
        while(low>=0 && data[low]==k)
            --low;
        while(high<data.size() && data[high]==k)
            ++high;
        return high-low-1;
    }
};
12.最大子方阵
有一个方阵，其中每个单元(像素)非黑即白(非0即1)，请设计一个高效算法，找到四条边颜色相同的最大子方阵。
给定一个01方阵mat，同时给定方阵的边长n，请返回最大子方阵的边长。保证方阵边长小于等于100。
测试样例：
[[1,1,1],[1,0,1],[1,1,1]],3
返回：3


class SubMatrix {
public:
    int maxSubMatrix(vector<vector<int> > mat, int n) {
        // write code here
        if(n == 0) return 0;
        vector<vector<int> > matA = mat;//坐标点下方连续1的个数
        vector<vector<int> > matB = mat;//坐标点右方连续1的个数
        vector<vector<int> > matAA = mat;//坐标点下方连续0的个数
        vector<vector<int> > matBB = mat;//坐标点右方连续0的个数
        int i,j;
        int len = 0;
        int wide;
        for(i=n-1;i>=0;--i){
            for(j=n-1;j>=0;--j){
                if(mat[i][j] == 0){
                    matA[i][j] = 0;
                    matB[i][j] = 0;
                    if(i == n-1){
                        matAA[i][j] = 1;
                    }else{
                        matAA[i][j] = matAA[i+1][j]+1;
                    }
                    if(j == n-1){
                        matBB[i][j] = 1;
                    }else{
                        matBB[i][j] = matBB[i][j+1]+1;
                    }
                }else {
                    if(i == n-1){
                        matA[i][j] = 1;
                    }else{
                        matA[i][j] = matA[i+1][j]+1;
                    }
                    if(j == n-1){
                        matB[i][j] = 1;
                    }else{
                        matB[i][j] = matB[i][j+1]+1;
                    }
                    matAA[i][j] = 0;
                    matBB[i][j] = 0;
                }
            }
        }
       for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                if(mat[i][j] == 0){
                    wide = min(matAA[i][j],matBB[i][j]);
                    while(wide>0){
                        if(matAA[i][j+wide-1] >= wide && matBB[i+wide-1][j] >= wide){
                            len = len<wide?wide:len;
                        }
                        wide--;
                    }
                }else{
                    wide = min(matA[i][j],matB[i][j]);
                    while(wide>0){
                        if(matA[i][j+wide-1] >= wide && matB[i+wide-1][j] >= wide){
                            len = len<wide?wide:len;
                        }
                        wide--;
                    }
                }
            }
        }
        return len;
    }
};