剑指offer数组题型总结篇

更新中…

类别
1.无序数组

概念：未经过排序的数组
优点：插入快
缺点：查找慢，删除慢，大小固定
2.有序数组

概念：数组中的元素是按照一定规则排列的。

优点：查找效率高。根据元素值查找时可以使用二分查找，效率比无序数组高很多，在数据量大的时候尤其明显。对于leetcode中很多查找元素类的题目，如果没有事先说明是有序数组，可以事先对数组进行排序，再进行查找，二分法或其他方法都可以。

缺点：插入和删除较慢。插入元素时，首先判断该元素的小标，然后对该小标之后的所有元素后移以为才能进行插入，所以有序数组比较适合查找频繁，而插入删除操作较少的情况。

1.二维数组中的查找
题目描述：

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

解题思路：
由于该二维数组上到下递增，左到右递增的特殊性，遍历整个矩阵进行查找不是该题目的意图所在。总结规律我们可以发现：应该从矩阵的右上角或者左下角开始查找。

以右上角为例，首先选取右上角的数字，如果该数字等于要查找的数字，则查找过程结束；如果该数字大于要查找的数字，则说明该列其他元素都大于要查找的数字，便可以删掉该列；如果该数字小于要查找的数字，则说明该行其他元素也都小于要查找的数字，便可以删掉该行。

这样，每一次比较都可以剔除一行或者一列，进而缩小查找范围，时间复杂度为O(n)。

java代码：

//从左下角开始查找
class Solution{
    
	public boolean find(int [][]arrays,int target)
	{
    
		if(arrays==null)
			return false;
		int row=arrays.length;//行数
		int col=arrays[0].length;//列数
		for(int i=row-1,j=0;i>=0 && j<col;)
		{
    
			if(arrays[i][j]==target)
				return true;
			else if(arrays[i][j]>target) //不可能在该行
				i--;
			else //不可能在该列
				j++;
		}
		return false;
	}
}

2.旋转数组的最小数字

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 给出的所有元素都大于0，若数组大小为0，请返回0。

解题思路：
如果整个数组是有序的，那我们一定会想到用折半查找来实现。对于旋转数组，我们发现，它实际上可以划分为两个排序的子数组，而且前面数组的元素都不小于后面数组的元素，并且最小值正好就是这两个数组的分界线，由此，我们可以得出以下解决方法。

首先用两个指针low和high分别指向数组的第一个元素和最后一个元素，然后可以找到中间元素mid。对于这个中间元素，有以下两种情况：（1）该元素大于等于low指向的元素，此时最小的元素说明在mid的后面，可以把low=mid；（2）中间元素小于等于high指向的元素，那么最小元素在mid之前，可以high=mid。特别注意：这里不要+1或者-1，因为只有这样才能保证low始终在第一个数组，high始终在第二个数组。依次循环，当最后low和high相差1时，low指向第一个数组的最后一个，high指向第二个数组的第一个（即为我们要找的最小值）。

很明显，以上查找的时间复杂度为O(logN)。

java代码：

public int minNumberInRotateArray(int [] array) {
    
        /* 三种情况： （1）把前面0个元素搬到末尾，也就是排序数组本身，第一个就是最小值 （2）一般情况二分查找，当high-low=1时，high就是最小值 （3）如果首尾元素和中间元素都相等时，只能顺序查找 */
        int len=array.length;
        if(len==0)
            return 0;
        int low=0,high=len-1;
        if(array[low]<array[high]) //排序数组本身
            return array[low];
        while(low<high){
    
            int mid=low+(high-low)/2;
            if(array[low]==array[mid] && array[high]==array[mid])
                return minInOrder(array);//这种情况只能顺序查找
            if(array[mid]>=array[low])
                low=mid;
            else if(array[mid]<=array[high])
                high=mid;
            if(high-low==1)
                return array[high];
        }
        return -1;
    }
    public int minInOrder(int [] array) {
     //顺序查找
         int min=array[0];
         for(int num:array){
    
             if(num<min)
                 min=num;
         }
          return min;
     }

3.K-Sum
​ 这类题目通常会给定一个数组和一个值，让求出这个数组中两个/三个/K个值的和等于这个给定的值target。

例题：TWO SUM（在一个数组中找到两个数字的和为目标值的数）
例如：target=5 arrays[5]={12,3,4,5,1} 数组中1+4等于目标值5，则返回它们对应的下标，不存在则返回0

解题思路：

1.暴力解法：最常见，但耗时较长，只能作为备选，

2.hash-map：建立一个hash-map循环遍历一次即可

3.two-pointers：定位两个指针根绝和的大小来移动另外一个。这里设定的指针个数根据题目中K的个数来定。3Sum中可以设定3个指针，固定两个，移动另一个。

//暴力法
class Solution{
    
	public int Two_Sum(int arrays[],int target)
	{
    
		for(int i=0;i<arrays.length;i++)
		{
    
			for(int j=1;j<arrays.length;j++)
			{
    
				if(arrays[i]+arrays[j]==target)
				{
    
					return i,j;
				}
			}
		}
	}
}

c++代码：

bool hash_twosum(int *array,int len,int target,int *i,int *j)//i,j表示结果的下标，开始为0
{
    
	map<int,int>index;  //索引
	map<int,int>::iterator it;  //值迭代器
	for(int x=0;x<len;x++)
	{
    
		index[array[x]]=x;//数组元素为 11,12,13,14,15 则索引index[11]=0 index[12]=1 index[13]=2 index[14]=3 index[15]=4
	}
	for(x=0;x<len;x++)
	{
    
		int other=target-array[x]; //剩下的数是否在数组中
		it=index.find(other); //若存在这个索引
		if(it!=index.end()&& it!=index.find(array[x]))//若找到或没到末尾
		{
    
			*i=x;
			*j=it->second;
			return true;
		}
	}
	return false;
}

//双指针法：
class Solution{
    
	public int Two_Sum(int arrays[],int target)
	{
    
		int left=0;
		int right=arrays.length-1;
		while(left<right)
		{
    
			if(arrays[left]+arrays[right]==target)
				return left,right;
			else if(arrays[left]+arrays[right]<target)
				left++;
			else if(arrays[left]+arrays[right]>target)
				right--;
		}
	}
}

拓展：在二叉树中查找two sum
解题思路：
中序遍历二叉树，将结果放入一个数组中，再用双指针来查找

//关键代码
void inoder(BTREE T,vector<int> &a)
{
    
	if(T==NULL)
		return ;
	inoder(T->lchild,a);
	a.push_back(T->data);
	inoder(T->rchild,a);
}

bool findtarget(BTREE T,int target)
{
    
	vector<int> a;
	inoder<T,a>; //a存放节点值
	int left=0,right=n-1;
while(left<right)
{
    
	if(a[left]+a[right] ==target)
		return left,right;
	else if(a[left]+a[right] <target)
		left++;
	else if(a[left]+a[right] >target)
		right--;
	else 
		return true;
}
return false;
}

4.判断数组中是否有重复数字
解题思路：用hash表直接一遍搞定，若有重复数字，则计数器加1

bool isrepeat(vector<int> &nums)
{
    
	map<int,int> dict;//用hash表,初始值全部为0
	for(num:nums)
	{
    
		dict[num]++;//数字相同的对应的下标的值加1
		if(dict[num]>1)
			return true;
	}
	return false;
}

5.区间问题
这类题目通常会给一个包含多个子数组的数组，然后针对区间是否重合来判断true or false。

解题技巧：

1.按start排序
2.在前一个区间的end和后一个区间的start找交集
例题:252 meeting room[easy]（https://leetcode.com/problems/meeting-rooms/）

题目理解：给定一个数组，包含每个会议的开始时间和结束时间[[s1,e1],[s2,e2],…],判断一个人能否参加所有的会议。

test case:

Example1:

Input: [[0,30],[5,10],[15,20]]Output: falseExample2:Input: [[7,10],[2,4]]Output: true

解题思路：在这个题目里，如果一个人要参加所有会议，那么所有会议的时间应该不能重合，所以只需要判断后一个会议开始的start > 前一个会议结束的end就就可以，如果end>start,就返回false。首先得先对所有子数组的start进行排序，然后再进行判断start和end

class Solution{
    
 
    public boolean canAttendMeetings(Interval[] intervals){
    
 
        Arrays.sort(intervals,(x,y)->(x.start-y.start));
 
        //i从1开始，因为涉及到判断前一个数组的end
 
        for (int i =1;i <intervals.length;i++){
    
 
            if (intervals[i-1].end > intervals[i].start){
    
 
                return false;
 
            }
        }
}

6.子数组类题目

这类题目通常会在一个包含多个子数组的数组中，求和/积，最大最小等。
解题技巧：

滑动窗口（sliding window）

例题：209 Minimum Size Subarray Sum[Medium]

题目理解：给定我们一个数字，让我们求子数组之和大于等于给定值的最小长度

test case:

Input: s = 7, nums = [2,3,1,2,4,3]

Output: 2

解释：满足子数组和=7的最小长度数组是[4,3],所以output=2

解题思路：求的数字要大于等于这个数字target，譬如这个testcase中，[2,3,1,2,4,3]，从前往后相加，前四项相加的和为8.已经大于7了，但是我们的target是7，后面的几项也都是正整数，继续往后走，肯定也会大于target7，所以这个时候我们把left指针往右移动一位，那么就是相当于成为了一个滑动窗口（sliding window）。

7.数组输出排列最小的数
例如： [2,23,234] 最小结果为223234

解题思路：因为涉及到数字可能会溢出，所以用字符串较合适，转换为字符串–> a+b b+a 比较 2 23–>23 2，将较小的数连在一起

#include<iostream>
#include<vector>
#include<string>
using namespace std;
static bool cmp(int a,int b)
{
    
	std::string A=std::to_string(a)+std::to_string(b);
	std::string B=std::to_string(b)+std::to_string(a);
	return A<B;
}
string print(vector<int> numbers)
{
    
	sort(numbers.begin(),numbers.end(),cmp);
	string s;
	for(int ai:numbers)
	{
    
		s+=to_string(ai);
	}
	return s;
}
int main()
{
    
	vector<int> numbers;
	print(numbers);
	return 0;
}

8.去掉有序数组中重复的数字,返回无重复数字的长度
解题思路：双指针法（覆盖法）

//i代表旧数组的索引，index代表新数组的索引，将无重复数依次移动到前面
int remove(vector<int> &a)   
{
    
	int i,index;
	index=1;//index为第二个数的索引
	if(a.empty())
		return 0;
	for(i=1;i<a.size();i++)//i和index均为第二个数的索引
	{
    
		if(a[i]!=a[index-1])   
		{
    
			a[index]=a[i];
			index++;//记录不重复数的个数
		}
	}
	return index;
}

9、调整数组顺序使奇数位于偶数前
解题思路：
1.用新的数组存储新的顺序,先扫描一遍数组，将奇数存入新的数组中，再扫描一遍数组将偶数存入数组中。比较耗费空间，不建议。
2.用双指针，若查找到一个奇数和一个偶数，则将它们互换位置。

//法一
#include<iostream>
#include<vector>
using namespace std;
void ReOrderArray(vector<int> &a)
{
    
	if(a.empty())
		return ;
	vector<int> result;
	for(int i=0;i<a.size();i++)
	{
    
		if(a[i]<<2==1)
			result.push_back(a[i]);
	}
	for(i=0;i<a.size();i++)
	{
    
		if(a[i]<<2==0)
			result.push_back(a[i]);
	}
	a=result;
}
int main()
{
    
	vector<int> a;
	int b[5]={
    1,2,3,4,5};
	for(int i=0;i<5;i++)
	{
    
		a.push_back(b[i]);
	}
	ReOrderArray(a);
	for(i=0;i<a.size();i++)
	{
    
		cout<<a[i]<<" ";
	}
	return 0;
}

数组的排列组合

题目描述：例如数组[1,2,3].其排列组合结果为[1,3,2],[2,1,3],[2,3,1],[3,2,1],[3,1,2],[1,2,3]

思路：把数组看成两部分，一部分是第一个数，另一部分是第一个数后面的所有数，拿第一个数与后面的所有数依次交换，很典型的递归思路；

void Fun()
{
    
	int a[5]={
    1,2,3,4,5];
	permutations(a,0,4);
}
void permutations(int a[],int m,int n)
{
    
	if(m==n)
	{
    
		for(int i=0;i<=n;i++)
		{
    
			cout<<a[i];
		}
		cout<<endl;
	}
	else
	{
    
		for(int j=m;j<=n;j++)
		{
    
			int temp=a[m];
			a[m]=a[i];
			a[i]=temp;
			permutations(a,m+1,n);
			temp=a[m];
			a[m]=a[i];
			a[i]=temp;
		}
	}
}

拓展：如果是求字符串的排列组合呢？
如果是求字符串的所有组合呢：例如有三个字符a,b,c,则它们的组合为a,b,c,ab,ac,bc,abc.