C语言算法实战：查找数组中符合特定位置条件的元素及双孤立数

问题一：查找位置受限的元素

第1步：理解题目约束与基础思路

目标是寻找数组中的所有整数 a[i]，使得其左侧所有元素均小于等于 a[i]，右侧所有元素均大于等于 a[i]。为了判断这一点，我们需要知道每个位置左侧的最大值（LeftMax）和右侧的最小值（RightMin）。

直观的解法是使用两个额外的辅助数组 pMax[] 和 pMin[]：

• pMax[i] 记录从索引 0 到 i 之间的最大值。
• pMin[i] 记录从索引 i 到数组末尾之间的最小值。

对于任意索引 i，如果 a[i] >= pMax[i-1] 且 a[i] <= pMin[i+1]，则该元素符合要求。

第2步：实现双辅助数组方案（Solution 1）

这种方法逻辑清晰，但需要 O(n) 的额外空间来存储两个数组。以下是标准实现的参考代码，包含了对边界条件（首尾元素）的检查：

//函数功能 ： 找元素 
//函数参数 ： 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++)    
    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--) 
    pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i]; 
 
  // 检查第一个元素
  if(pArray[0] <= pMin[0])   
    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]) 
    cout<<pArray[len-1];
  cout<<endl; 
 
  // 释放内存
  delete [] pMin; 
  delete [] pMax; 
  pMin = pMax = NULL; 
}

第3步：优化为单额外数组方案（Solution 2）

根据题目“只用一个额外数组和少量其它空间”的要求，我们可以省去 pMax 数组。因为 Max[i] 是自左往右计算的，而我们的判断过程也是自左向右遍历，完全可以在循环中用一个局部变量 Max 实时保存当前的左侧最大值。

1. 预处理：依然需要一个 pMin[] 数组来存储后缀最小值（需反向遍历生成）。
2. 动态更新：在正向遍历判断时，维护变量 Max 表示 a[0]...a[i-1] 的最大值。

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--) 
    pMin[i] = (pMin[i+1] <= pArray[i])? pMin[i+1]: pArray[i]; 
 
  // 检查第一个元素
  if(pArray[0] <= pMin[0])   
    cout<<pArray[0]<<' '; 
 
  // 遍历中间元素，动态更新Max
  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) 
    cout<<pArray[len-1];
  cout<<endl; 
 
  delete [] pMin; 
  pMin = NULL; 
}

问题二：找出数组中两个只出现一次的数字

第1步：问题分析与 XOR 特性回顾

题目描述：整型数组中除了两个数字外，其他数字均出现两次。要求时间复杂度 O(n)，空间复杂度 O(1)。

核心知识点：

• 任何数与自身异或结果为 0（即 x ^ x = 0）。
• 任何数与 0 异或结果为其自身（即 x ^ 0 = x）。
• 异或运算满足交换律和结合律。

第2步：整体异或获取差异标志

如果只有一个孤立数字，直接将所有数异或即可得到答案。现在有两个孤立数字（设为 A 和 B），将所有数字异或后的结果 all 必然不等于 0。这意味着 all 的二进制表示中至少有一位是 1。

这个为 1 的位，意味着 A 和 B 在该位上一个是 0，一个是 1。这就是我们将数组分为两组的关键依据。

第3步：按位分组再次异或

找到 all 中任意一个为 1 的位（通常找最低位的 1），以此为基准将数组划分为两部分：

1. 该位为 1 的数字归为一组。
2. 该位为 0 的数字归为另一组。

A 和 B 分别落入这两个组，而其他成对的相同数字会被分到同一组并互相抵消为 0。最后对两组分别进行全量异或，即可得到 A 和 B。

//函数功能 ： 找出数组中两个只出现一次的数字 
//函数参数 ： arr为源数组，len为数组元素个数，result用来存放结果  
//返回值 ：  无 
void FindIsolateTwo(int *arr, int len, int *result) 
{ 
  int i, all = 0, flag = 1; 
  
  // Step 1: 所有数字异或，得到 A ^ B 的结果
  for(i = 0; i < len ; i++) 
    all ^= arr[i]; 
 
  // Step 2: 寻找过滤位（即 A^B 中第一个不为0的位）
  while(!(all&flag)) 
    flag <<= 1; 
 
  result[0] = result[1] = 0; 
  
  // Step 3: 根据过滤位将数字分入两组并分别异或
  for(i = 0; i < len; i++) 
  { 
    if(flag&arr[i]) 
      result[0] ^= arr[i]; // 该位为1的一组
    else 
      result[1] ^= arr[i]; // 该位为0的一组
  }
}