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

问题描述:一个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];
  }
}
(0)

相关推荐

  • C语言中交换int型变量的值及转换为字符数组的方法

    不使用其他变量交换两个整型的值: #include <stdio.h> void main(){ int a = 3; int b = 4; a = a ^ b;//使用异或交换 b = b ^ a; a = a ^ b; printf("%d, %d\n", a, b); a = a - b;//使用加减交换 b = a + b; a = b - a; printf("%d, %d\n", a, b); a ^= b ^= a ^= b; printf

  • 使用C语言实现vector动态数组的实例分享

    下面是做项目时实现的一个动态数组,先后加入了好几个之后的项目,下面晒下代码. 头文件: # ifndef __CVECTOR_H__ # define __CVECTOR_H__ # define MIN_LEN 256 # define CVEFAILED -1 # define CVESUCCESS 0 # define CVEPUSHBACK 1 # define CVEPOPBACK 2 # define CVEINSERT 3 # define CVERM 4 # define EXP

  • C语言中数组作为函数的参数以及返回值的使用简单入门

    函数通过数组作为参数 如果想通过一个一维数组作为函数的参数,就必须声明函数形式参数,使用以下三种方式与所有三个声明方法之一产生类似的结果,因为每一种方式告诉编译器,一个整数指针将会要被接收.类似的方式,可以使用多维数组形式参数. 方式-1 形式参数为指针如下.在下一章将学习什么是指针. void myFunction(int *param) { . . . } 方式-2 如下形式数组参数的大小: void myFunction(int param[10]) { . . . } 方式-3 如下形式

  • C语言一维数组初步学习笔记

    数组 可以存储一组或者多组数值的变量,里面包含多个元素,数组的每个成员都是一个数组元素. 一维数组 定义:类型 数组名[常量表达式] = {值1, 值2, 值3-}; int a[3] = {0, 1, 2}; float f[2] = {1.2, 2.3, 3.14}; char str[] = {'h', 'e', 'l', 'l', 'o'}; chat str1 = "iPhone";//这也是定义字符数组的方法,字符数组后面会详细讲解,这里先了解一下 当数组元素个数为变量时,

  • C语言 数组指针详解及示例代码

    数组(Array)是一系列具有相同类型的数据的集合,每一份数据叫做一个数组元素(Element).数组中的所有元素在内存中是连续排列的,整个数组占用的是一块内存.以int arr[] = { 99, 15, 100, 888, 252 };为例,该数组在内存中的分布如下图所示: 定义数组时,要给出数组名和数组长度,数组名可以认为是一个指针,它指向数组的第 0 个元素.在C语言中,我们将第 0 个元素的地址称为数组的首地址.以上面的数组为例,下图是 arr 的指向: 下面的例子演示了如何以指针的方

  • 直观理解C语言中指向一位数组与二维数组的指针

    一维数组和指针: 对于一位数组和指针是很好理解的: 一维数组名: 对于这样的一维数组:int a[5];  a作为数组名就是我们数组的首地址, a是一个地址常量 . 首先说说常量和变量的关系, 对于变量来说, 用箱子去比喻再好不过了, 声明一个变量就声明一个箱子,比如我们开辟出一个苹果类型的箱子, 给这个变量赋值就是把盛放苹果的箱子中放入一个实实在在的苹果, 这就是变量的赋值.  而对于数组来说, 就是一组类型相同的箱子中,一组苹果箱子, 可以放入不同的苹果. 一维数组空间: 变量被声明后, 我

  • C语言数组指针的小例子

    1.功能:输入6个学生的5门课程成绩,计算出每个学生的平均分和每门课程的平均分.2.C语言实现代码:(其实就是用二维数组来实现的,二维数组的引用传递使用数组指针来完成) 复制代码 代码如下: #include <stdio.h>#define STUDENT 5#define SCORE 6void input_array(float (*score)[STUDENT]);void avg_score(float (*score)[STUDENT]);void avg_course(float

  • 简单分析C语言中指针数组与数组指针的区别

    首先来分别看一下,指针数组的一个小例子: #include <stdio.h> #include <string.h> int lookup_keyword(const char*key, const char* table[], const int size) { int ret = -1; int i = 0; for(i=0; i<size; i++) { if (strcmp(key, table[i]) == 0) { ret = i; break; } } ret

  • C语言将数组中元素的数排序输出的相关问题解决

    问题描述:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个.例如输入数组{32,  321},则输出这两个能排成的最小数字32132.请给出解决问题的算法,并证明该算法.       思路:先将整数数组转为字符串数组,然后字符串数组进行排序,最后依次输出字符串数组即可.这里注意的是字符串的比较函数需要重新定义,不是比较a和b,而是比较ab与 ba.如果ab < ba,则a < b:如果ab > ba,则a > b:如果ab = ba,则a = b.比较

  • C语言中二维数组指针的简要说明

    C语言中,指针是一个复杂但又灵活多变的知识点,我们知道,在一维数组中,对于一个数组a[],*a,a,&a,都表示a的首地址,但如果与二维数组混合使用,就显得更为复杂了.例如对于一个二维数组 a[2][4]={{1,2.3},{4,5,6}} a+i,&a[i],*(a+i),a[i], 这四个表达式到底表示什么呢? 先告诉答案吧,其实这几个表达式都是指向同一个地址的,也许你会很诧异,也会很疑惑,怎么会是这样呢!!事实证明就是这样的, C语言中,指针是一个复杂但又灵活多变的知识点,我们知道,

  • 一波C语言字符数组实用技巧集锦

    字符数组倒序 #include <stdio.h> void daoxu(char str[]){ int i; char temp; for(i = 0; i < strlen(str) / 2 ; i ++){ temp = str[i]; str[i] = str[strlen(str) - i-1]; str[strlen(str) - i-1] = temp; } } 单词计数    int wordCount(char str[]){ int i; int count = 0

随机推荐