C语言找出数组中的特定元素的算法解析

  • 更新时间:2022-12-02 14:14:13
  • 编辑:厉俊豪

     问题描述:一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],其左边的数都小于等于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。
      思路:如果能用两个辅助数组,那么相对来说简单一点,可定义数组Min和数组Max,其中Min[i]表示自a[i]之后的最小值(包括a[i]),Max[i]表示自a[i]之前元素的最大值。有了这两个辅助数组后,对于a[i],如果它大于Max[i-1]并且小于Min[i+1],那么就符合要求。
      但是题目要求是只用一个额外数组,其实Max数组可以省去,完全可以边判断边计算,这是因为Max[i]是自左往右计算的,而判断时也是自左往右,两个过程正好可以合起来。只需用一个变量Max保存一下当前的最大值即可。下面给出两种方法的代码实现。
      参考代码:

//函数功能 : 找元素 
//函数参数 : pArray指向数组,len为数组的元素个数 
//返回值 : 无 
void FindElements_Solution1(int *pArray, int len) 
{ 
  if(pArray == NULL || len <= 0 ) 
    return ; 
 
  int *pMin = new int[len]; 
  int *pMax = new int[len]; 
  int i; 
 
  pMax[0] = pArray[0]; 
  for(i = 1; i < len; i++)    //计算自i往前最大值的辅助数组 
    pMax[i] = (pMax[i-1] >= pArray[i])? pMax[i-1]: pArray[i]; 
  pMin[len-1] = pArray[len-1]; 
  for(i = len - 2; i >= 0; i--) //计算自i开始最小值的辅助数组 
    pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i]; 
 
  if(pArray[0] <= pMin[0])   //检查第1个元素是否满足条件 
    cout<<pArray[0]<<' '; 
  for(i = 1; i < len - 1; i++) 
  { 
    if(pArray[i] >= pMax[i-1] && pArray[i] <=pMin[i+1]) //满足这个关系式的元素符合要求 
      cout<<pArray[i]<<' '; 
  } 
  if(pArray[len-1] >= pMax[len-1]) //检查第len个元素是否满足条件 
    cout<<pArray[i]; 
  cout<<endl; 
 
  delete [] pMin; 
  delete [] pMax; 
  pMin = pMax = NULL; 
} 

void FindElements_Solution2(int *pArray, int len) 
{ 
  if(pArray == NULL || len <= 0 ) 
    return ; 
 
  int *pMin = new int[len]; 
  int Max; 
  int i; 
 
  Max = pArray[0]; 
  pMin[len-1] = pArray[len-1]; 
  for(i = len - 2; i >= 0; i--) //计算自i开始最小值的辅助数组 
    pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i]; 
 
  if(pArray[0] <= pMin[0])   //检查第1个元素是否满足条件 
    cout<<pArray[0]<<' '; 
 
  for(i = 1; i < len - 1; i++) 
  { 
    if(pArray[i] >= Max && pArray[i] <=pMin[i+1]) //满足这个关系式的元素符合要求 
      cout<<pArray[i]<<' '; 
    Max = (Max < pArray[i])? pArray[i]: Max; //更新当前最大值 
  } 
  if(pArray[len-1] >= Max) //检查第len个元素是否满足条件 
    cout<<pArray[i]; 
  cout<<endl; 
 
  delete [] pMin; 
  pMin = NULL; 
} 

找出数组中两个只出现一次的数字(数组)
 问题描述:一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
     思路:如果只有一个数字只出现一次,而其他都出现两次,则直接将所有数字做一次异或运算即可,因为相等的数字异或一下结果为0。如果有两个数字只出现一次,而其他数字出现了两次。该怎么办呢?《编程之美》一书提供了一种方法,即先将所有数字做一次异或运算,得到一个数字,然后以该数字的某非0位作为过滤位,将数组分成两个部分,此时只出现一次的数字会被分到不同的部分。现在问题就转为只出现一次的情况,对每部分分别做异或运算即可。
     参考代码:

//函数功能 : 找出数组中两个只出现一次的数字 
//函数参数 : arr为源数组,len为数组元素个数,result用来存放结果  
//返回值 :  无 
void FindIsolateTwo(int *arr, int len, int *result) 
{ 
  int i, all = 0, flag = 1; 
 
  for(i = 0; i < len ; i++) //所有数异或 
    all ^= arr[i]; 
 
  while(!(all&flag)) //寻找过滤位 
    flag <<= 1; 
 
  result[0] = result[1] = 0; 
  for(i = 0; i < len; i++) //利用过滤位区分 
  { 
    if(flag&arr[i]) 
      result[0] ^= arr[i]; 
    else 
      result[1] ^= arr[i]; 
  } 
} 

 

相关教程

  • C语言代码实现扫雷小游戏

    C语言代码实现扫雷小游戏

    给大家整理一篇关于C语言的教程,这篇文章主要为大家详细介绍了C语言代码实现扫雷小游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2022-07-04

  • C语言文件操作总结

    本篇文章给大家通过代码示例讲述了C语言文件操作的相关知识点,对此有兴趣的朋友可以参考学习下。

    发布时间:2022-04-06

  • C语言实现C++继承和多态的实例内容

    本文主要给大家简单讲诉了C和C++的区别以及如何使用C语言模拟实现C++继承和多态,并附上示例代码,是篇相当不错的文章,推荐给喜欢C语言的小伙伴们

    发布时间:2021-06-10

  • C语言数据输入与输出实例详解

    这篇文章主要介绍了C语言数据输入与输出实例详解的相关资料,需要的朋友可以参考下

    发布时间:2022-04-16

  • C语言链表实现销售管理系统

    C语言链表实现销售管理系统

    给网友朋友们带来一篇关于C语言的教程,这篇文章主要为大家详细介绍了C语言链表实现销售管理系统,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2022-06-26

  • C语言实现自动给QQ好友发窗口抖动

    这篇文章主要介绍了C语言实现自动给QQ好友发窗口抖动,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2021-05-07

  • 深度剖析C语言结构体

    给大家整理一篇关于C语言的教程,今天小编就为大家分享一篇关于深度剖析C语言结构体,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧

    发布时间:2022-07-25

  • C语言原码、反码、补码和移码知识点总结

    这篇文章主要介绍了C语言基础 原码、反码、补码和移码详解的相关资料,需要的朋友可以参考下

    发布时间:2021-06-02

用户留言