每日一题——力扣26. 删除有序数组中的重复项（举一反三）

一个认为一切根源都是“自己不够强”的INTJ

个人主页：用哲学编程-CSDN博客
专栏：每日一题——举一反三

我的写法：

代码点评：

时间复杂度分析：

空间复杂度分析：

总结：

我要更好！

这种方法体现了以下哲学和编程思想：

举一反三！

题目链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/

我的写法：

// 定义一个函数，用于移除数组中的重复元素，并返回新数组的长度
int removeDuplicates(int* nums, int numsSize) {// 如果数组只有一个元素，那么它没有重复，直接返回1if(numsSize==1){return 1;}// 初始化变量：i 用于记录不重复元素的位置，j 用于遍历数组，xor 用于异或操作，counts_re 用于记录重复元素的数量int i,j,xor,counts_re;// 初始化循环变量，xor 初始化为数组的第一个元素，counts_re 初始化为0for(i=0,j=1,xor=nums[0],counts_re=0;j<numsSize;j++){// 对当前元素和 xor 进行异或操作，xor 初始为前一个元素的值xor^=nums[j];// 如果异或结果为0，说明当前元素与前一个元素相同，计数器 counts_re 增加if(xor==0){counts_re++;}else{// 如果异或结果不为0，说明当前元素与前一个元素不同，将当前元素移动到 i 指向的位置，并增加 ii++;nums[i]=nums[j];}// 更新 xor 为当前元素的值，以便下一次循环使用xor=nums[j];}// 返回原数组长度减去重复元素的数量，即新数组的长度return numsSize-counts_re;
}

这段代码的目的是移除数组中的重复元素，并返回新数组的长度。下面是对这段代码的专业点评，包括时间复杂度和空间复杂度的分析：

代码点评：

逻辑清晰：代码的逻辑是清晰的，通过异或操作来判断相邻元素是否相同，这是一种有效的比较方法。
边界条件处理：代码考虑了数组只有一个元素的情况，并正确处理了这种边界条件。
双指针技术：使用 i 和 j 两个指针来遍历数组，i 用于记录不重复元素的位置，j 用于遍历整个数组，这是一种常见的双指针技术。
重复计数：通过 counts_re 变量来记录重复元素的数量，这是一种有效的计数方法。
原地修改：代码在原数组上进行修改，没有使用额外的数组空间，这有助于节省内存。

时间复杂度分析：

时间复杂度：这段代码的时间复杂度是 O(n)，其中 n 是数组的长度。这是因为代码使用了一个循环来遍历整个数组，每个元素只被访问一次。

空间复杂度分析：

空间复杂度：这段代码的空间复杂度是 O(1)，即常数级别的额外空间使用。这是因为代码只使用了几个额外的变量（i、j、xor、counts_re），并没有使用与输入规模成比例的额外空间。

总结：

这段代码是一个有效的方法，用于移除数组中的重复元素，并返回新数组的长度。它的时间复杂度是 O(n)，空间复杂度是 O(1)，表明它是一个高效的解决方案。不过其中的变量xor是多余的。

我要更好！

要去除 xor 变量并保持代码功能不变，可以直接比较当前元素 nums[j] 和它前一个元素 nums[i]。当两者不相等时，应当将 nums[j] 移动到 nums[i+1] 的位置，并增加 i 的值，这样可以保持 nums[i] 始终指向最新的不重复元素的位置。

修改后的代码：

int removeDuplicates(int* nums, int numsSize) {// 如果数组大小小于或等于1，它要么为空，要么已经没有重复元素if (numsSize <= 1) return numsSize;// i 用于记录最新的不重复元素的位置int i = 0; // 从第一个元素开始，i 指向最后一个不重复元素的位置for (int j = 1; j < numsSize; j++) {// 当前元素与前一个不重复的元素比较if (nums[j] != nums[i]) {// 当发现不重复的元素时，移动到i的下一个位置i++;nums[i] = nums[j];}}// 新数组长度为最后一个不重复元素的索引 + 1return i + 1;
}

这个版本，去掉了 xor 变量，这样做的好处是简化了逻辑，同时避免了对异或操作的不必要依赖。原本的 xor 逻辑更多是为了理解异或操作如何工作，而在实际应用中直接比较相邻元素通常更直接和易于理解。这个改进的版本仍旧遵循 O(n) 的时间复杂度和 O(1) 的空间复杂度，适用于大多数需要去重复元素的场景。

这种方法体现了以下哲学和编程思想：

简洁性（Simplicity）：通过去除不必要的变量（如 xor），代码变得更加简洁和易于理解。这种简洁性是编程中的一个重要原则，因为它有助于减少错误和提高代码的可维护性。
增量式开发（Incremental Development）：代码逐步构建，每次只处理一个元素，确保每个步骤都是正确的。这种增量式的方法有助于在开发过程中及时发现和纠正问题。
迭代（Iteration）：使用循环（for 循环）来遍历数组中的每个元素，这是编程中处理重复任务的常用方法。迭代是编程中的一个基本概念，它允许程序重复执行相同的代码块，直到满足某个条件。
抽象（Abstraction）：通过函数 removeDuplicates 将去重逻辑封装起来，使得调用者不需要关心具体的实现细节，只需要知道函数的功能和输入输出。这种抽象有助于提高代码的可读性和可重用性。
单一职责原则（Single Responsibility Principle）：函数 removeDuplicates 只负责一个任务，即移除数组中的重复元素。这种单一职责原则有助于保持代码的清晰和模块化。
空间和时间的权衡（Space-Time Tradeoff）：虽然原始代码使用了一个额外的变量 xor，但修改后的代码避免了这种空间上的开销，同时保持了时间复杂度为 O(n)。这种权衡是算法设计中的一个常见考虑因素。
函数式编程思想（Functional Programming）：虽然这段代码是命令式的，但它体现了函数式编程中的一些思想，如避免副作用（函数内部的操作不改变输入数组以外的状态）和使用纯函数（给定相同的输入，总是产生相同的输出）。
实用主义（Pragmatism）：代码的目的是解决问题，而不是追求理论上的完美。在这个例子中，通过实际的比较操作来移除重复元素，而不是使用理论上可能更优雅但实际应用中可能更复杂的解决方案。