时间戳

首页 > 解决方案 > 5 月 Leetcode Speedrun 问题：有序数组中的单个元素

c++ - 5 月 Leetcode Speedrun 问题：有序数组中的单个元素

问题描述

所以我看着 Errichto 完成了这些挑战，我对他解决“排序数组中的单个元素”的速度感到惊讶。从初学者的角度来看，它看起来确实令人印象深刻——也许对于高级开发人员来说，速度是很正常的。

给定一个排序数组，其中所有元素都是整数，并且所有元素在数组中恰好出现两次，除了一个元素只出现一次。（即，所有元素都是重复的，除了一个。）您需要找到恰好出现一次的元素。

我只是在这里了解所述代码的工作原理：

class Solution { 
public:
    int singleNonDuplicate(vector<int>& nums) {
        long long a = 0;
        for(int x : nums) {
            a ^= x
        }
        return a;
    }
};

这是我到目前为止所得到的： 对于向量/数组“nums”中的每个整数“x”，a 等于 a^x（如果我说的是正确的话）。

这是我的问题：

a^x 不会等于 0，因为 a 从一开始就是 0 吗？

int singleNonDuplicate(vector<int> nums) {
//...
}

and

int singleNonDuplicate(vector<int>& nums) {
//...
}

我已经理解这一点：按值传递vector<int> nums（您正在函数内部使用 nums 的“副本”）并且通过引用传递（您正在函数内部使用 nums 本身）。vector<int>& nums

如果您要像 Errichto 那样解决问题，“&”是否重要？

ps：

  1. 抱歉，从编程的角度来看可能出现的错误，我可能不小心说了一些错误的话。
  2. 是的，我迟早会学习 C++，2020 年是我生命中的第一年，我的日程安排中实际上有一个真正的“编程”课程，这些视频很有趣，我很想知道为什么所说的代码有效并尝试理解等.

标签： c++arraysvector

解决方案

休闲证明：

（如果您对可以帮助您提出此类解决方案并理解它们的研究领域感兴趣，我建议您使用离散数学和群论/抽象代数。）

我想我知道你提到的问题。它是这样的，

给定一个未排序的数组，其中所有元素都是整数，并且所有元素在数组中恰好出现两次，除了一个元素只出现一次。（即，所有元素都是重复的，除了一个。）

你在第一部分的正确轨道上，为什么算法有效。它利用了 XOR 的一些特性：

  • X^0=X
  • X^X=0
  • XOR 操作是可交换的和关联的。
# proof

# since XOR is commutative, we can take advantage
# of the fact that all elements except our target
# occur in pairs of two:

P1, P1 = Two integers of the same value in a pair.
T = Our target.

# sample unsorted order, array size = 7 = (3*2)+1
[ P3, P1, T, P1, P2, P3, P2 ]

# since XOR is commutative, we can re-arrange the array
# to our liking, and still get the same value as
# the XOR algorithm.

# here, we move our target to the front, and then group
# each pair together.  I've arranged them in ascending
# order, but that's not important:

[ T, P1, P1, P2, P2, P3, P3 ]

# write out the equation our algorithm is solving:
solution = 0 ^ T ^ P1 ^ P1 ^ P2 ^ P2 ^ P3 ^ P3

# because XOR is associative, we can use parens
# to indicate elements of the form X^X=0:
solution = T ^ (P1 ^ P1) ^ (P2 ^ P2) ^ (P3 ^ P3) ^ 0

# substitute X^X=0
solution = T ^ 0 ^ 0 ^ 0 ^ 0

# use X^0=X repeatedly
solution = T

所以我们知道运行那个算法会给我们我们的目标，T。

关于使用&传递引用而不是传递值：

你的理解是正确的。在这里，它并没有真正的区别。

Pass-by-reference 允许您修改原始值，而他没有这样做。

Pass-by-value 复制向量，这不会对这里的性能产生有意义的影响。

所以他获得了使用 pass-by-reference 的风格点，如果你使用 leetcode 来证明你作为一名软件开发人员的勤奋，很高兴看到，但这与他的解决方案无关。

推荐阅读