两道常见的经典数组问题

末蓝、 2024-03-31 17:15 71阅读 0赞

#### 目录 ####

*   *  1~100连续数，99大小的数组，怎么找出没有出现的那一个？
     *   *  等差数列求和
         *  在原数组上进行下标标记
     *  变形：有奇数个无规律的数字（都是很大的数字），但是都是两两出现，只有一个数字是单身只出现了一次，找出他
     *   *  巧妙地^运算

### 1~100连续数，99大小的数组，怎么找出没有出现的那一个？ ###

> 想必这道题大家都见怪不怪了;我的第一反应是，开一个100单位的数组，将原数组的值按照下标映射进新数组，出现的话新数组的位置就会置为1，之后再遍历新数组就知道哪个下标为0，则他就是没有出现的！ **时间O(n)空间O(n)**

int src[99];//原数组
    int arr[101];//新开的数组
    for(auto&e:src){
        
    	arr[e] = 1;
    }
    for(int i = 1;i<101;i++){
        
        if(arr[i]==0){
        
            cout<<i<<endl;
            break;
        }
    }

当然上述计数排序的映射思想很简单能想到，但是如果题目要求不能额外的开数组或者使用容器呢？要求：空间复杂度为O(1)

那么，我们只能在原数组上进行操作，这里有两种方式:

#### 等差数列求和 ####

> 由于源数组src是不重复的 1~100的99个数字; **那么我们把1~100相加的值算出来，与数组的99个元素相减**，剩下的不就是没有在数组中出现的了吗…6 **空间O(1)!**

//等差数列前n项和公式n(a1+an)/2;
    int src[99];//原数组
    int sum = 100*(1+100)/2;//等差数列计算1~100的和
    
    for(auto&e:src){
        
        sum-=e;
    }
    cout<<sum<<endl;

#### 在原数组上进行下标标记 ####

上述能直接套用数学公式进行计算的条件也是很苛刻的，比如1~100的数字不会在src原数组重复出现！ **那万一有重复出现的可能呢**？那么1~100这100个数字在源src99大小数组中没有出现的数字，可能就不止一个了，数学公式的方式肯定用不了了，\*\*要求求出全部没在源数组中出现的1~100的数字呢？？？ 当然空间还是要求O(1)不然又是计数排序开新数组的下表映射思想了;

> 我们在原数组上进行下表映射标记: 那么怎么在标记的基础上，不会影响标记位置的值呢？ (如何对数组中的一个元素进行处理，使他能达到**标记**的效果，又不会**丢失**他原先的值)
> 
> 答案是: **取相反数**！ 比如src\[0\]为数字1，我们把这个1映射到src\[1\]的位置，让**src\[1\] = -src\[1\]**; 这样，我们**看到了负数，代表他的index 1是出现过的**！同时我们也**不会丢失src\[1\]原本的数字**，只需要处理的时候，将这个负数取回正数即可！

int src[99];//原数组
    
    for(int i=0;i<100;i++){
        
        //注意这个x是1~100，我们的src源数字只有合法下标0~98 这99个数字，小心越界,注意边界处理; 我们单独处理99，和100两个数字即可
        int x = abs(src[i]);//处理为正数，代表出现这个数，让他作为下标 进行映射;  
    
        //映射-->取相反数 当然，本来就是负的不用处理;
        if(src[x-1]>0) src[x-1]*=-1;
    }
    
    for(int i = 0;i<100;i++){
        
        if(src[i]>0){
        //非负数，没被标记，没出现过
            cout<<i+1<<' ';
        }
    }

当然，上述代码其实只需要特殊判断100就行了，因为我们可以把0下标也运用起来，每次src\[x-1\]\*=-1;这样标记，但是后续输出也得cout<<i+1<<’ '才是对应意义的数字，有点麻烦，我就直接标记的方式，多次粗来了99这个数组，语义更清晰！

**上述原地标记的一个条件**也是，我们提前知道了存的数字只能是1~100中的哦，意味着**存的数字个数是100个，下标连续！ 数组大小是99**，基本全放得下对应的映射;**但**如果存了val相差最大1000个这种，那么只有99or100个大小的数组，显然原地标记的方法行不通，会越界等等！

### 变形：有奇数个无规律的数字（都是很大的数字），但是都是两两出现，只有一个数字是单身只出现了一次，找出他 ###

#### 巧妙地^运算 ####

这个位运算，直接异或操作遍历一遍即可;

> ^异或运算有，a^a=0，任何两个相同的数异或为0 **0^b=b，0异或任何数为那个数本身**;
> 
> **^交换率**: a^a^b=a^b^a = b; 类似于密码学的加解密！ a^b产生密文m， b自己^m就解密，^出了a;

int src[奇数];//原数组
    int sum = 0;
    
    for(auto&e:src){
        
        sum^=e;
    }
    cout<<sum<<endl;