数组中的趣味题（一）

我不是女神ヾ 2022-07-16 12:11 156阅读 0赞

[数组中的趣味题（一）][Link 1]

**　　无论是参加面试还是笔试，数组都是常考的内容，并且考察数组的知识往往结合着比较有意思的算法。在这里参照网上的资料和平时看过的相关书籍总结一下，作为自己的面试复习材料吧。我知道这个总结肯定有遗漏或者是不对的地方，希望大家看到可以优化和改正的的地方，帮帮忙给点新思路吧。谢谢大家~~**

**1.求数组中的最大值（最小值）**

--------------------

**问题描述：**给定一个整数数组arr，找出其中的最大值（最小值）。

**解决思路：**传统的方法就是遍历一次数组即可得到最大值（最小值），时间复杂度是O（N）；现在说另外一个思路利用二分，即将数组分成元素数目接近相等的两部分，然后分别找到两个部分的的最大值（最小值），最后合并，比较两个部分的最大值（最小值），即可得到最终的最大值（最小值）。

**代码：**

![ExpandedBlockStart.gif][] FindMax

![复制代码][copycode.gif]

1 int FindMax(int *arr,int l,int r)
     2 {
     3     if(l == r)
     4     {
     5         return arr[l];
     6     }
     7     int mid = (l+r)/2;
     8     int LMAX,RMAX;
     9     LMAX = FindMax(arr,l,mid);
    10     RMAX = FindMax(arr,mid+1,r);
    11     return max(LMAX,RMAX);
    12 }

![复制代码][copycode.gif]

**2.求数组中出现次数超过一半的元素**

--------------------

**问题描述：**整数数组arr中，一定存在一个数x，x在数组arr中出现的次数过半，请找出这个数x。

**解决思路：**既然x在数组中出现的个数过半，那么若将数组arr排序，显然数组中arr\[N/2\]一定是要找的x（N数组arr中元素的个数）。这个思路的时间复杂度取决于排序算法的时间复杂度，因此整个算法的时间复杂度达到O(N\*logN)是没有问题的。既然x在数组arr中出现的次数过半，那么在遍历数组的过程中若每次遇到与x不同的数，x出现的数目-1，出现x，则x出现的数目+1，那么到最后剩下的一定是x。这种情况下，只需要遍历一次数组，时间复杂度是O(N)，但是，难点是我们事先不知道x是什么，那么算法怎么实现呢？看看代码就明白啦~~

**代码：**

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 int Find(int *arr,int n)
     2 {
     3     int tmp = arr[0];
     4     int count = 1;//计数器
     5     for(int i = 1 ; i < n ; i++)
     6     {
     7         if(count == 0)
     8         {
     9             tmp = arr[i];
    10             count = 1;
    11         }
    12         else if(tmp == arr[i])
    13         {
    14             count++;
    15         }
    16         else
    17         {
    18             count--;
    19         }
    20     }
    21     return tmp;
    22 }

![复制代码][copycode.gif]

**3.求数组中元素间的最近距离（一）**

--------------------

**问题描述：**数组arr\[\]中存在N个元素（数组中N个元素没有范围），找到这样的a和b，使得abs（a，b）的值最小。

**解决思路：**这是个比较简单的问题了，思路也很容易想到，只需要将arr进行排序，这时数组中元素的最短距离只可能是相邻的两个元素之间，这个算法的时间复杂度是：O(N\*logN)。如果不对数组进行排序，那么就需要枚举数组中的每两个元素了，求出最小距离，时间复杂度是O(N\*N)。

**代码：**

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 int MinDistance(int *arr,int n)
     2 {
     3     int tmp_MIN = INF;
     4     //假设INF是arr中两个数相加能得到的最大值
     5     sort(arr,arr+n);
     6     for(int i = 0 ; i < n-1; i++)
     7     {
     8         if(arr[i+1] - arr[i] < tmp_MIN)
     9         {
    10             tmp_MIN = arr[i+1] - arr[i];
    11         }
    12     }
    13     return tmp_MIN;
    14 }

![复制代码][copycode.gif]

**4.求数组中元素间的最近距离（二）**

--------------------

**问题描述：**和上一个问题相似，区别是arr中的数组元素的取值范围的。

**解决思路：**既然加了一个条件，那么看来就是利用这个条件进行优化了。既然数组中的元素有了范围，不妨先假设数组中值在0~100之间，那么我们可以这样做，申请一个数组bool fuzhu\[100\]，这样遍历一遍数组，记录arr中出现的元素，假设arr中包含4，那么arr\[4\]=1，然后在遍历一遍fuzhu，fuzhu\[i\]值为1，表示i存在于arr中，这样计算“相邻”的fuzhu\[\]=1的元素，计算出最小距离。用一个大家看书时比较不愿意看到的词：经分析，时间复杂度是O(N+M)，其中M是aar中元素的所在区间大小。

**代码：**

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 int MinDistance(int *arr,int n)
     2 {
     3     bool fuzhu[101];
     4     int first,second;
     5     int tmp_MIN = INF;
     6     memset(fuzhu,false,sizeof(fuzhu));
     7     //遍历找出在arr出现的数
     8     for(int i = 0 ; i < n ; i++)
     9     {
    10         fuzhu[arr[i]] = true;
    11     }
    12     int j = 0;
    13     while(j < 101 && !fuzhu[j])
    14     {
    15         j++;
    16     }
    17     first = j++;//获取fuzhu中第一个不为0的数
    18     while(j < 101 && !fuzhu[j])
    19     {
    20         j++;
    21     }
    22     second = j++;//获取fuzhu中第二个不为0的数
    23     while(1)
    24     {
    25         if(second - first < tmp_MIN)
    26         {
    27             tmp_MIN = second - first;
    28         }
    29         while(j < 101 && !fuzhu[j])
    30         {
    31             j++;
    32         }
    33         if(j > 100) break;
    34         first = second;
    35         second = j++;
    36     }
    37     return tmp_MIN;
    38 }

![复制代码][copycode.gif]

**小结：**大家看后，肯定会说arr中数组范围也可能是负数啊，那怎么办呢？注意了，这个题要求的是，最近距离。下标虽然不能为负，但是只要移位存储就完事了吗！毕竟只需要最小距离啊，平行移动不影响最小距离。比如arr中元素的范围是-100~~100，那么只需要当出现-100，对应的fuzhu\[-100+100\] = fuzhu\[0\] = true。不就可以了吗？

**5.求两个数组中的相同元素**

--------------------

**问题描述：**现在有两个已经排好序的整数数组arr1和arr2，找出两个数组中的相同元素。

**解决思路：**既然已经排好序了，那么问题就简单了，假设arr1\[2\]和arr2\[4\]相等，那么搜索arr1\[3\]只需要和arr2中下标4及以后的元素比较。如果arr1和arr2中元素的个数分别是N和M，那么这个算法的时间复杂度是O(N+M)，不妨先看看代码。

**代码：**

![ExpandedBlockStart.gif][]

![复制代码][copycode.gif]

1 // 找出两个数组的相同元素
     2 void FindSame(int *arr1, int *arr2,int n,int m)
     3 {    
     4     int i = 0;    
     5     int j = 0 ;    
     6     while (i < n && j < m)    
     7     {        
     8         if (arr1[i] < arr2[j])            
     9             ++i;        
    10         else if(arr1[i] == arr2[j])        
    11         {            
    12             cout<<arr1[i]<<endl;
    13             ++i;            
    14             ++j;    
    15         }       
    16         else//arr1[i] > arr2[j]    
    17             ++j ;   
    18     }
    19 }

![复制代码][copycode.gif]

**小结：**对于这个问题arr1和arr2数组都已经是排好序的，那么如果两个数组都不是排好序的呢？？后来在网上查了点资料，发现这样一个哈希的思路：遍历一遍arr1，建立哈希表，然后遍历一遍arr2，看看哪一个元素存在于哈希表中。这样一来时间复杂度还是O(N+M)，但是多引入了O(N)的空间复杂度。在这里：**求高手给出哈希的C++代码！！！**

[Link 1]: http://www.cnblogs.com/BeyondAnyTime/archive/2012/07/17/2593224.html
[ExpandedBlockStart.gif]: /images/20220716/aada42d42081446899814e244077c3cd.png
[copycode.gif]: /images/20220716/149bd518d7cd45478159ae603104993e.png