559-双指针思想解决数组问题

逃离我推掉我的手 2022-09-11 10:11 113阅读 0赞

## 将字符串逆序 ##

**采用双指针的思想**  
分别指向数组的首元素和末尾元素  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_15_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]

//逆序字符串
    void Reverse(char arr[], int size)
    {
        
        char* p = arr;
        char* q = arr + size - 1;
        while (p < q)
        {
        
            char ch = *p;
            *p = *q;
            *q = ch;
            p++;
            q--;
        }
    }
    int main()
    {
        
        char arr[] = "hello world";
        Reverse(arr, strlen(arr));
        cout << arr << endl;
    }

## 整形数组，把偶数调整到数组的左边，把奇数调整到数组的右边 ##

![在这里插入图片描述][c8b915a3a39f4343b67852f4e000a01e.png]  
我们采用双指针的思想  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**我们要把右边的偶数放左边，左边的奇数放右边**  
p指针就是从最左边向右找奇数，然后q指针从右向左找偶数，当p从左向右找到1个奇数，q从右向左找到1个偶数，就把p指针指向的奇数和q指针指向的偶数一交换，这样一来，就把右边的偶数放左边，左边的奇数放右边了  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]

处理交换完之后，p后移，q前移

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]  
然后重复刚才的过程。  
**直到p和q相遇，退出while循环。**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_10_color_FFFFFF_t_70_g_se_x_16]

#include <iostream>
    #include <stdlib.h>
    #include <time.h>
    #include <string.h>
    using namespace std;
    
    //整形数组，把偶数调整到数组的左边，把奇数调整到数组的右边
    void AdjustArray(int arr[], int size)//接收数组的首地址，数组的个数 
    {
        
        int* p = arr;
        int* q = arr + size - 1;
    
        while (p < q)
        {
        
            //p->从左向右找奇数
            while (p < q)
            {
        
                if ((*p & 0x1) == 1)//是奇数了，因为只有奇数的第一位是1 
                {
        
                    break;
                }
                p++;//是偶数，继续向后走 
            }
    
            //q <- 偶数
            while (p < q)
            {
        
                if ((*q & 0x1) == 0)//是偶数 
                {
        
                    break;
                }
                q--;//是奇数，继续向前走 
            }
    
            //p->奇数   q->偶数
            if (p < q)
            {
        
                int tmp = *p;
                *p = *q;
                *q = tmp;
                p++;
                q--;
            }
        }
    }
    int main()
    {
        
        int arr[10] = {
         0 };
        srand(time(0));//每次运行随机数是不一样的，随系统时间不断变化 
        for (int i = 0; i < 10; i++)
        {
        
            arr[i] = rand() % 100;
        }
    
        for (int v : arr)
        {
        
            cout << v << " ";
        }
        cout << endl;
    
        AdjustArray(arr, 10);
        for (int v : arr)
        {
        
            cout << v << " ";
        }
        cout << endl;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

## 移除元素问题 ##

![在这里插入图片描述][9afa0f7dc53c4dbea4785be918e935d9.png]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
**把val值的元素都调整到末尾**  
**我们采用双指针的思想**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]  
**我们就是把右边残留的不等于val的元素的值放到左边等于val的元素上**  
**返回的数组的长度**就是p移动到的位置减去数组的首地址  
q从右向左找不等于val的元素， p从左向右找等于val的值，如果找到，就q解引用赋值给p的解引用  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_16_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 3]  
p==q，这个元素也是要判断的。如果这个元素等于val值3，这个值就不记录，p-首元素地址=1，长度就是1，没有问题。如果这个值不等于val，p还要往后加一下  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
不满足while的条件，跳出，**所以我们的while条件要修改一下(p<=q)**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16]  
**p-首元素地址=2，刚好是2,2，长度是2**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
**优化代码一下**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16 1]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/098689c775734aa18a26d845ee31b169.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e26b3a7bdbf949e5aae61ee6ec79a0e9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_14_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/8099165f77874b60bf87745b48391148.png
[c8b915a3a39f4343b67852f4e000a01e.png]: /images/20220828/86340d1e526f481c9b69a04cc0a6f1b3.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/e9d8c806a8914db6b5b1b05f507dcbb0.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d958040c68564333ad580f2ab6eb4f5c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/01069e842efb41ba96f6496fd10d1b0c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/b8fbfa88eb4d4ef586bfd9a8f892cccf.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/9fbdb32c0c34433fae52d585f6efdb3b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/da370c5c5e2d42648e6eb9f557d51bdd.png
[9afa0f7dc53c4dbea4785be918e935d9.png]: /images/20220828/4df16411391042afb20e33740b239b22.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/feda17e6165e4e1ba1fa3673b8a5b186.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/5d315fb168434f2c9216024d90ac42a2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/bf5a87a86fed4283859834f598927c13.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/48827c4af9324e04ad7b625255916d3c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/62d9795f0cb642a6889e8078d35b6982.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_18_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/72fc4a6821d449e5ba9586d2e4a5eadd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/857832fab7cd468e90e208f4915e0932.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/5ff3934384fb48d285d9d41e15ca4b9b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/d88458ef1d3d4c25821273ae0487db62.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_12_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/ae6519a766104c168ee5a693de4e85d9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/53acc3d00b3f4daab27905e6667e37d9.png