数组中相关面试题

ゝ一纸荒年。 2023-01-19 09:41 26阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、移除元素
 *   *   *  1.题目描述
         *  2.解题思路
 *  二、删除有序数组中的重复项
 *   *   *  1.题目描述
         *  2.解题思路
 *  三、合并两个有序数组
 *   *   *  1.题目描述
         *  2.解题思路
 *  四、旋转数组
 *   *   *  1.题目描述
         *  2.解题思路
 *  五、数组形式的整数加法
 *   *   *  1.题目描述
         *  2.解题思路
 *  总结

# 前言 #

--------------------

![在这里插入图片描述][20210509161315305.png]

# 一、移除元素 #

[移除元素][Link 1]

### 1.题目描述 ###

1.  给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
2.  说明:为什么返回数值是整数，但输出的答案是数组呢?请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。  
    你可以想象内部操作如下:  
    ![在这里插入图片描述][20210509161738356.png]  
    ![在这里插入图片描述][20210509161758503.png]  
    ![在这里插入图片描述][20210509161833727.png]

### 2.解题思路 ###

1.  思路1:定义变量如果当前元素 j 与移除元素 val 相同，那么跳过该元素。如果当前元素 xj与移除元素 val 不同，那么我们将其放到下标 j的位置，并让 j自增右移,最终得到的 j 即是答案。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]  
    代码如下：

int removeElement(int* nums, int numsSize, int val)
    { 
        int i=0;
        int j=0;
        for(i=0;i<numsSize;i++)
        { 
            if(nums[i]!=val)
            { 
                nums[j]=nums[i];
                j++;
            }
        }
        return j;

1.  思路2:定义两个下标，如果val不等于下标所在的值，则两下标同时加加，否则一个下标加加,返回只加一个下标的值。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]  
    代码如下：

int removeElement(int* nums, int numsSize, int val)
    { 
     int dest=0;
        int src=0;
        while(src<numsSize)
        { 
            if(nums[src]==val)
            { 
                src++;
            }
            else
            { 
                nums[dest]=nums[src];
                dest++;
                src++;
            }
        }
        return dest;
    }

# 二、删除有序数组中的重复项 #

[删除有序数组中的重复项][Link 2]

### 1.题目描述 ###

1.  给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
2.  说明:为什么返回数值是整数，但输出的答案是数组呢?请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。  
    你可以想象内部操作如下:  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]  
    ![在这里插入图片描述][20210509170012984.png]  
    ![在这里插入图片描述][20210509170024845.png]

### 2.解题思路 ###

1.  思路1:定义index值为0，用for循环遍历一次，里面用if条件判断，如果数组中的值不等于下标index的值，则index往前一步，最后返回index+1  
    代码如下：

int removeDuplicates(int* nums, int numsSize)
    { 
    	if (numsSize < 2)
    	{ 
    		return numsSize;
    	}
    	int index = 0;
    	for (int i = 1; i < numsSize; i++)
    	{ 
    		if (nums[i] != nums[index])
    		{ 
    			nums[++index] = nums[i];
    		}
    	}
    	return index + 1;
    }

1.  思路2:定义三个下标next=1,prev=0;cur=0。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]  
    代码如下：

int removeDuplicates(int* nums, int numsSize)
    { 
        if(numsSize==0)
        { 
            return 0;
        }
        int dest=0;
        int cur=0;
        int next=1;
        while(next<numsSize)
        { 
            if(nums[cur]!=nums[next])
            { 
                nums[dest]=nums[cur];
                cur++;
                next++;
                dest++;
            }
            else
            { 
                while(next<numsSize && nums[cur]==nums[next])
                { 
                    next++;
                }
                nums[dest]=nums[cur];
                dest++;
                cur=next;
                next++;
            }
        }
        if(cur<numsSize)
        { 
            nums[dest]=nums[cur];
            dest++;
        }
        return dest;
    }

# 三、合并两个有序数组 #

[合并两个有序数组][Link 3]

### 1.题目描述 ###

1.  给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。  
    ![在这里插入图片描述][20210509171006188.png]  
    ![在这里插入图片描述][20210509171014932.png]

### 2.解题思路 ###

1.  定义数组长度为num1数组长度加num2数组长度，如果num1数组的值大于num2数组的值，则把num1数组的值放到下标为m+n-1的num1中反之把num2的值放进去。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]  
    代码如下：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
    { 
        int end1=m-1;
        int end2=n-1;
        int end=m+n-1;
        while(end1 >= 0 && end2 >=0)
        { 
            if(nums1[end1]>nums2[end2])
            { 
                nums1[end]=nums1[end1];
                end1--;
                end--;
            }
            else 
            { 
                nums1[end]=nums2[end2];
                end2--;
                end--;
            }
        }
        
        while(end2 >= 0)
        { 
            nums1[end]=nums2[end2];
            end2--;
            end--;
        }
    }

# 四、旋转数组 #

[旋转数组][Link 4]

### 1.题目描述 ###

1.  给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。进阶：  
    尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。  
    你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

### 2.解题思路 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 7]  
思路三代码:  
代码如下：

void reverse(int* arr,int left,int right)
    { 
        while(left<right)
        { 
        int tmp=0;
        tmp=arr[left];
        arr[left]=arr[right];
        arr[right]=tmp;
        left++;
        right--;
        }
    }
    void rotate(int* nums, int numsSize, int k)
    { 
        k=k%numsSize;
        reverse(nums,0,numsSize-k-1);
        reverse(nums,numsSize-k,numsSize-1);
        reverse(nums,0,numsSize-1);
    }

# 五、数组形式的整数加法 #

[数组形式的整数加法][Link 5]

### 1.题目描述 ###

1.  对于非负整数 X 而言，X 的数组形式是每位数字按从左到右的顺序形成的数组。例如，如果 X = 1231，那么其数组形式为 \[1,2,3,1\]。给定非负整数 X 的数组形式 A，返回整数 X+K 的数组形式。  
    ![在这里插入图片描述][20210509171726571.png]  
    ![在这里插入图片描述][2021050917173555.png]  
    ![在这里插入图片描述][20210509171743572.png]  
    ![在这里插入图片描述][20210509171750713.png]

### 2.解题思路 ###

代码如下：

/** * Note: The returned array must be malloced, assume caller calls free(). */
    int* addToArrayForm(int* num, int numSize, int k, int* returnSize)
    { 
        int kSize=0;
        int n=k;
        while(n)
        { 
            ++kSize;
            n=n/10;
        }
        int len=kSize>numSize?kSize+1:numSize+1;  //求出最后相加数的位数
        int* retArr=(int*)malloc(sizeof(int)*len);
    
        int Ai=numSize-1;
        int Ki=0;
        int next=0;
    
        int reti=0;
    
        while(Ai>=0||Ki<kSize)
        { 
            int aval=0;
            if(Ai>=0)  //把num数组的元素放到aval中
            { 
                aval=num[Ai];
                Ai--;
            }
    
            int KVal=k%10;
            k=k/10;
            Ki++; //算出k的每一位的值
    
            int ret=aval+KVal+next;  //相同的位加起来
            if(ret>=10)
            { 
                next=1;
                ret=ret-10;
            }
            else
            { 
                next=0;
            }
    
            retArr[reti]=ret;  //反着过来放数据
            reti++;
        }
    
        if(next==1)  //如果数进了位
        { 
            retArr[reti]=1;
            reti++;
        }
    
        int begin=0;
        int end=reti-1;
        while(begin<end)
        { 
            int tmp=retArr[begin];
            retArr[begin]=retArr[end];
            retArr[end]=tmp;
            begin++;
            end--;
        }
        *returnSize=reti;
        return retArr;
    }

--------------------

# 总结 #

以上就是今天要讲的内容，本文仅仅简单介绍了数组中常见的几道面试题，对于以后面试我们可能会遇到，希望大家掌握。还有，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。

![在这里插入图片描述][20210509171942845.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/02bbef9648144a5b97cdebeedfe7fe18.png
[20210509161315305.png]: /images/20221021/5a7f7fd61ba54138b8b70b363113771c.png
[Link 1]: https://leetcode-cn.com/problems/remove-element/
[20210509161738356.png]: /images/20221021/26e6c2c6ba0a46da9365a0175b1a0559.png
[20210509161758503.png]: /images/20221021/f0a41e15b56a41988f6caa33818ef225.png
[20210509161833727.png]: /images/20221021/6ca78f6de06e43ad813fc561a63d9e31.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221021/8dcb22bc05bb4880ba04a760ade27cda.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221021/eaccc06ed6274e18aa0e32f92e6fd2cb.png
[Link 2]: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 2]: /images/20221021/ea0254ee27a4439684949d5c1acc4d85.png
[20210509170012984.png]: /images/20221021/9a0d610a102644c8b99a39b2bc09437a.png
[20210509170024845.png]: /images/20221021/6a23353a9ae64cc98aa7c922eb1f35a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 3]: /images/20221021/069a993bf9a54923a9e0260b90859aed.png
[Link 3]: https://leetcode-cn.com/problems/merge-sorted-array/
[20210509171006188.png]: /images/20221021/9d430625c74e44578081d4a5cca889f7.png
[20210509171014932.png]: /images/20221021/26d8abe2682045138516305df9c7d061.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 4]: /images/20221021/4875de9a5fb34bf191e59c55172897c6.png
[Link 4]: https://leetcode-cn.com/problems/rotate-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 5]: /images/20221021/f087fc0b908540bebf50896d805032b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 6]: /images/20221021/18a03668d2a349c5b379ff89d1541f33.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 7]: /images/20221021/5647e1a7ed23417a99c0dc6fdc6960f3.png
[Link 5]: https://leetcode-cn.com/problems/add-to-array-form-of-integer/
[20210509171726571.png]: /images/20221021/86a13ae24df5465fb0220d45e1607ed8.png
[2021050917173555.png]: /images/20221021/89226311a2ce4c208c01bc0ddfde93c5.png
[20210509171743572.png]: /images/20221021/6b00537e791f423591bb7be8e32eca5b.png
[20210509171750713.png]: /images/20221021/2c58e7b7c6ef47409c320a007a2319a8.png
[20210509171942845.png_pic_center]: /images/20221021/08466b2366b545baa750345379b61d98.png