面试经典150题——删除有序数组中的重复项

server/2024/11/14 15:01:09/

目录

题目链接:26. 删除有序数组中的重复项 - 力扣(LeetCode)

题目描述

判题标准:

示例

提示:

解法一:双指针

Java写法:

运行时间

C++写法:

运行时间

论屎山代码是如何出现的

时间复杂度和空间复杂度

总结


题目链接:26. 删除有序数组中的重复项 - 力扣(LeetCode)

注:下述题目描述和示例均来自力扣

题目描述

给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过:

  • 更改数组 nums ,使 nums 的前 k 个元素包含唯一元素,并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

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 = [1,1,2]
输出:2, nums = [1,2,_]
解释:函数应该返回新的长度 2,并且原数组 nums 的前两个元素被修改为 1, 2 。
不需要考虑数组中超出新长度后面的元素。

示例 2:

输入: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 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 已按 非严格递增 排列


解法一:双指针

        在给定的整数数组(或在这个例子中是std::vector<int>)中移除重复项,使得每个元素最多只出现两次,并返回移除重复项后数组的新长度(即不包含被移除元素的部分)。不过,根据代码的实际逻辑,它实际上是在原地(in-place)修改数组,移除所有重复超过两次的元素,并返回剩余元素(即不重复或只重复一次)的数量。这里有一点小误解,因为通常“移除重复项”的表述可能意味着删除所有重复项,只保留唯一的元素,但这段代码实际上是保留最多两次出现的元素。

具体实现思路如下:

  1. 初始化指针:使用两个指针(或在这个例子中的索引变量)来遍历数组。一个指针(或索引)change用于跟踪当前应该放置新元素(即不重复或只重复一次的元素)的位置,另一个指针(或索引)findToChange用于遍历整个数组以查找下一个可能的新元素。

  2. 遍历数组:通过循环遍历数组(从第二个元素开始,因为第一个元素总是可以被视为“新元素”),比较findToChange指向的元素与findToChange - 1指向的元素是否相等。

  3. 比较与替换

    • 如果不相等,说明找到了一个新的元素(或该元素尚未达到两次出现),则将其复制到change指向的位置,并将changefindToChange都向前移动一位,以便继续查找下一个新元素。
    • 如果相等,说明当前元素是重复的,且前一个元素与它相同,因此不需要将其复制到新位置。只需将findToChange向前移动一位,以继续检查下一个元素。
  4. 返回结果:当遍历完整个数组后,change指针(或索引)将指向最后一个新元素之后的位置,即数组应该被截断的位置。因此,change的值(作为索引)就是移除重复项后数组的新长度。

  5. 注意:虽然这段代码没有显式地“删除”或“移除”任何元素,但它通过覆盖重复元素并返回新长度的方式,在逻辑上实现了移除重复项的效果。如果需要物理上从数组中删除元素,那么可能需要使用支持动态大小调整的容器(如std::vector),并在最后调用resize方法来截断数组到新的长度。不过,在这个特定的实现中,由于std::vector的大小并未改变,只是返回了一个表示有效元素数量的新长度,因此没有必要进行物理删除。

Java写法:

class Solution {public int removeDuplicates(int[] nums) {int len = nums.length;int change = 1;int findToChange = 1;while(findToChange < len){// 0,0,1,1,1,2,2,3,3,4//   l rif(nums[findToChange] != nums[findToChange - 1]){// 如果前后的值不相等的话就替换一下nums[change] = nums[findToChange];// 赋值完成之后就指针全部后移change++;findToChange++;}else {findToChange++;}}// 最后change指针所在的位置就是合理数组的长度return change;}
}

运行时间


C++写法:

class Solution {  
public:  int removeDuplicates(std::vector<int>& nums) {  int len = nums.size();  int change = 1;  int findToChange = 1;  while (findToChange < len) {  // 检查当前元素是否与前一个元素相等  if (nums[findToChange] != nums[findToChange - 1]) {  // 如果不相等,则将当前元素放到change指针指向的位置  nums[change] = nums[findToChange];  // 指针后移  change++;  }  // 无论是否相等,findToChange都需要后移以检查下一个元素  findToChange++;  }  // 最后change指针所在的位置(也就是下一个应该放置新元素的位置)即为无重复元素数组的长度  return change;  }  
};

运行时间


论屎山代码是如何出现的

class Solution {public int removeDuplicates(int[] nums) {// 获取原数组的长度int len = nums.length;// 定义出指针int change = 1;int findToChange = 1;int resLen = 1;while(findToChange < len && change < len){// 定位好初始的位置if(change == findToChange && nums[change] != nums[change - 1]){change++;findToChange++;resLen++;}else{// change指针就位了if(nums[findToChange] == nums[change]){findToChange++;}else {while(findToChange < len && nums[findToChange - 1] == nums[findToChange]){findToChange++;}if(findToChange < len){// findToChange指针就位了nums[change] = nums[findToChange];change++;findToChange++;resLen++;}}}}return resLen;}
}

        

        虽然也是过了,但是想的实在是复杂的要死,这种就是一开始没想明白就开始写,然后发现BUG,改BUG,代码屎山就是这样来的。

时间复杂度和空间复杂度


总结

        想好再写,先狠狠的思考一波再写兄弟们,不然容易整出屎山代码哦shift


http://www.ppmy.cn/server/119774.html

相关文章

华为云服务综合实验

一、实验需求 本次实验内容基于华为云平台模拟企业web集群的构建&#xff0c;其中涉及的知识点包括Linux系统知识、nginx服务的安装及配置应用、云数据库 RDS(Relational Database Service,简称RDS)、虚拟私有云vpc、安全组、SFS弹性文件服务器以及负载均衡等。要求学生通过本…

开源 AI 智能名片小程序:开启内容营销新境界

摘要&#xff1a;本文深入探讨了在当今数字化时代&#xff0c;内容营销的重要性以及如何实现让用户主动找你的最佳效果。通过引入开源 AI 智能名片小程序这一创新工具&#xff0c;阐述了其在明确目标用户群体、迎合用户需求痛点和打造风格特色方面的独特优势&#xff0c;为企业…

鸿蒙OS 线程间通信

鸿蒙OS 线程间通信概述 在开发过程中&#xff0c;开发者经常需要在当前线程中处理下载任务等较为耗时的操作&#xff0c;但是又不希望当前的线程受到阻塞。此时&#xff0c;就可以使用 EventHandler 机制。EventHandler 是 HarmonyOS 用于处理线程间通信的一种机制&#xff0c…

Oracle(129) 如何使用闪回归档(Flashback Archive)?

闪回归档&#xff08;Flashback Archive&#xff09;是Oracle数据库提供的一个功能&#xff0c;用于长期存储表的历史数据。通过启用和配置闪回归档&#xff0c;你可以查询表的历史数据&#xff0c;而不需要依赖撤销段或归档日志。这对于审计、合规性和历史数据分析非常有用。 …

OpenAI API key not working in my React App

题意&#xff1a;OpenAI API 密钥在我的 React 应用中不起作用 问题背景&#xff1a; I am trying to create a chatbot in my react app, and Im not able to generate an LLM powered response. Ive been studying documentation and checking out tutorials but am unable …

JavaWeb JavaScript 11.XML —— 配置文件

生活想埋没我&#xff0c;没想到我是颗种子 —— 24.9.19 一、XML 1.什么是XML XML是EXtensible Markup Languge的缩写&#xff0c;翻译过来就是可扩展标记语言。所以很明显&#xff0c;XML和HTML一样都是标记语言&#xff0c;也就是说它们的基本语法都是标签 可扩展 三个字…

RetrievalAttention——提高 LLM 处理长上下文的效率

概述 论文地址&#xff1a;https://arxiv.org/abs/2409.10516 本文的研究背景主要是为了解决 "具有长语境的大型语言模型&#xff08;LLM&#xff09;"问题。基于变换器的 LLM 被广泛应用于各个领域&#xff0c;但在处理长上下文时&#xff0c;其计算成本非常高。特…

(undone) 学习语音学中关于 i-vector 和 x-vector

来源&#xff1a;https://ieeexplore.ieee.org/stamp/stamp.jsp?tp&arnumber8461375 (这是一篇跟 X-vector 有关的论文) 这里有更适合初学者的两个资料: 1.https://www.youtube.com/watch?vR3rzN6JYm38 &#xff08;MIT教授的youtube视频&#xff09; 2.https://people.c…