| 数据结构初步（四） | 您所在的位置：网站首页 › php输入数字排序 › 数据结构初步（四） |
|
前言 前面学习了顺序表的相关概念后，让我们来会会这几个题！ 1. 移除元素1.1 题目链接力扣（LeetCode）链接：移除元素 1.2 题目要求给你一个数组 nums和一个值 val，你需要 原地 移除所有数值等于 val的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1)额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 说明: 为什么返回数值是整数，但输出的答案是数组呢? 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下: // nums是以“引用”方式传递的。也就是说，不对实参作任何拷贝 int len = removeElement(nums, val); // 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }1.3 代码框架 int removeElement(int* nums, int numsSize, int val){ }1.4 思路分析(1)给定一个数组 nums，遇到与 val的数组元素相等就去掉，不相等就保留，假设 count是数组 nums中与 val相等元素的个数，则修改后的数组前 (numsSize-count)个位置是存放非 val的有效位置。 (2)题目要求空间复杂度是 O(1)，不能开辟额外的临时数组空间。 (3)我们可以把题目所给的原数组 nums当作修改元素后的新数组，两个变量记录数组下标，假设 p1记录原数组下标， p2记录新数组下标； count记录原数组中与 val相等的元素个数。 (4)开始时 p1、p2的下标都是 0，分别对应新旧数组的第一个位置，如果 p1位置的元素等于 val， p1、p2均往后后移动一位；否则，就把 p1位置元素放入 p2位置处，然后 p1往后移动一位。直到旧数组被 p1遍历一遍。 时间复杂度 O(n)空间复杂度 O(1)1.5 代码实现int removeElement(int* nums, int numsSize, int val){ int p1=0; int p2=0; int count = 0;//重复的数的个数 //初始下标p1与p2均为0 //下标p1遍历整个旧数组，下标p2指向新数组 while(p1 < numsSize){ if(nums[p1] != val){ nums[p2++] = nums[p1++]; } else{ ++p1; ++ccount; } } return numsSize - count; }2. 移除元素2.1 题目链接力扣（LeetCode）链接：删除有序数组中的重复项 2.2 题目要求一个 升序排列 的数组 nums，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组 nums的第一部分。更规范地说，如果在删除重复项之后有 k个元素，那么 nums的前 k个元素应该保存最终结果。 将最终结果插入 nums的前 k个位置后返回 k。 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1)额外空间的条件下完成。 判题标准: //系统会用下面的代码来测试你的题解: int[] nums = [...]; // 输入数组 int[] expectedNums = [...]; // 长度正确的期望答案 int k = removeDuplicates(nums); // 调用 assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; }如果所有断言都通过，那么您的题解将被 通过。 示例 1： 输入： nums = [0,0,1,1,1,2,2,3,3,4]输出： 5, nums = [0,1,2,3,4]解释：函数应该返回新的长度 5， 并且原数组 nums的前五个元素被修改为 0, 1, 2, 3, 4。不需要考虑数组中超出新长度后面的元素。 提示： 1 |
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 |