《剑指offer》数组相关面试题

╰+攻爆jí腚メ 2022-05-15 15:10 193阅读 0赞

### 文章目录 ###

*   *  一、找数组中重复的数字
     *  二、不修改数组找重复数字
     *  三、二维数组中的查找

## 一、找数组中重复的数字 ##

> 在一个长度为n的数组里所有数字都在0~n-1范围内。数组中某些数字是重复的，但不知道有几个数字重复，也不知道重复了几次，请找出数组中任意一个重复的数字。例如，长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出应该是重复的数字2或者3.

思路：重排这个数组，从头到尾依次扫描这个数组中的每个数字。扫到下标为i的数字m时：首先判断m是否等于i：是—扫描下一个数字；不是—判断它和第m个数字是否相等，若相等则找到了一个重复数字，若不相等则交换下标为i和m的数字。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BlcmZlY3RtYXRjaF9H_size_16_color_FFFFFF_t_70]

int duplication(int numbers[],int length)
    {
    	int i = 0;
    	int temp = 0;
    	if(numbers==NULL || length<=0){
    		return 0;
    	}
    	for(i=0;i<length;i++)
    	{
    		if(numbers[i]<0||numbers[i]>length-1)
    			return 0;
    	}
    	for(i=0;i<length;i++)
    	{
    		if(numbers[i]!=i)
    		{
    			if(numbers[i] == numbers[numbers[i]])
    			{
    				printf("%d", numbers[i]);
    				return 1;
    			}
    			temp = numbers[i];
    			numbers[i] = numbers[temp];
    			numbers[temp]= temp;
    		}
    	}
    	return 0;
    }

*当输入的数组中存在重复数字返回1，否则返回0，算法时间复杂度O（n），空间复杂度O(1).*

## 二、不修改数组找重复数字 ##

> 长度为n+1的数组里所有数字在1-n内，故至少有一个数字是重复的，找出数组中任意一个重复数字，例如\{2,3,5,4,3,2,6,7\}

思路：将1-n从中间的数字m分为两部分：1–m及m+1–n，若1+m中的数字出现次数大于m,则1–m中一定有重复数字，否则重复数字在m+1–n中，重新划分区间直到找到重复数字。

int getDuplication(const int numbers[],int length)
    {
    	int count = 0;
    	int start = 1;
    	int end = length-1;
    	int middle = 0;
    	if(numbers == NULL||length<=0){
    		return -1;
    	}
    	
    	while(end>=start)
    	{
    		middle = ((end-start)>>1)+start;
    		count = countRange(numbers,length,start,middle);
    		if(end == start)
    		{
    			if(count>1)
    				return start;
    			else 
    				break;
    		}
    		if(count>(middle-start+1))
    			end = middle;
    		else
    			start = middle+1;
    	}
    	return -1;
    }
    int countRange(const int numbers[],int length,int start,int end)
    {
    	int count = 0;
    	int i = 0;
    	if(numbers == NULL)
    		return 0;
    	for(i=0;i<length;i++)
    	{
    		if(numbers[i]>=start && numbers[i]<=end)
    			++count;
    	}
    	return count;
    }

## 三、二维数组中的查找 ##

> 在一个二维数组中，每一行从左到右递增，每一列从上到下递增。输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。在如下数组找7：

思路：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BlcmZlY3RtYXRjaF9H_size_16_color_FFFFFF_t_70 1]  
首先选取数组右上角的数字，如果该数字等于要查找的数字，则查找过程结束：如果该数字大于要查找的数，则剔除这个数字所在列；如果该数字小于要查找的数，则剔除这个数字所在行。

int Find(int* matrix,int rows,int columns,int number)
    {
    	if(matrix != NULL && rows>0 && columns>0)
    	{
    		int r = 0;
    		int c = columns-1;
    		while(r<rows && c>=0)
    		{
    			if(matrix[r*columns+c]==number)
    			{
    				return 1;
    			}
    			else if(matrix[r*columns+c]>number)
    			{
    				c--;
    			}
    			else
    				r++;
    		}
    	}
    	return  0;
    }

*也可以选取右上角和左下角的数字进行查找，但不可以选择左上角或右下角的进行查找。*

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BlcmZlY3RtYXRjaF9H_size_16_color_FFFFFF_t_70]: /images/20220503/6dc1096456fa4591aaedf24855956b4b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BlcmZlY3RtYXRjaF9H_size_16_color_FFFFFF_t_70 1]: /images/20220503/974b53228bef42f4981d08a112d90c44.png