文章目录
- 01 | 👑 题目描述
- 02 | 🔋 解题思路
- STL法
- 双指针法
- 03 | 🧢 代码片段
- STL法
- 双指针法
“Success is not final, failure is not fatal: It is the courage to continue that counts.” - Winston Churchill
01 | 👑 题目描述
给你一个整数数组，数组中的数可以是正数、负数、零，请实现一个函数，返回这个数组中所有数的平方值中有多少种不同的取值
对于这个题目的理解是，给定一个整数数组，我们需要找出数组中所有数的平方值中有多少种不同的取值。换句话说，我们需要统计数组中平方值的不同取值的数量。
02 | 🔋 解题思路
STL法
为了解决这个问题，我们可以使用一个集合（Set）来存储平方值的不同取值。我们遍历整数数组中的每个数，并计算其平方值。然后，将平方值添加到集合中。由于集合的特性是不允许重复元素，所以它只会保存不同的平方值。最后，我们返回集合的大小，即不同平方值的数量。
例如，对于输入数组 [1, 2, -3, 2, 0, -1, 3]，经过计算得到的平方值数组是 [1, 4, 9, 4, 0, 1, 9]。将这些平方值添加到集合中，得到的集合是 {0, 1, 4, 9}，其中有4个不同的平方值。因此，最终结果就是 4。
这样的解题思路可以确保我们只计算不同平方值的数量，而不会重复计算相同的平方值。
-
具体解题思路如下：
-
创建一个空集合（set）来存储平方值的不同取值。
-
遍历整数数组中的每个数。
-
对于每个数，计算其平方值。
-
将平方值添加到集合中。由于集合的特性是不允许重复元素，所以只会保存不同的平方值。
-
最后，返回集合的大小，即不同平方值的数量。
-
-
流程概括如下：
-
创建一个空的集合，用来存储不同平方值。
-
遍历整数数组中的每个数。
a. 计算当前数的平方值。
b. 将平方值添加到集合中。
-
返回集合的大小，即不同平方值的数量。
-
- 时间 && 空间复杂度
双指针法
参考STL法的思路，只要保证返回结果中的平方值都是唯一的即可，那么就可以采用排序和双指针法进行解题。
-
具体的解题流程：
-
对整数数组进行排序；
-
创建一个变量 count，初始值为 0。
-
设置两个指针，left 指向数组的开头，right 指向数组的末尾。
-
当 left <= right 时，执行以下步骤：
a. 计算指针 left 指向的数的平方值 squareLeft。
b. 计算指针 right 指向的数的平方值 squareRight。
c. 如果 squareLeft 等于 squareRight，表示找到了一个新的平方值，将 count 加 1，并同时将 left 和 right 向内缩小一个位置。
d. 如果 squareLeft 大于 squareRight，说明 left 指向的数的平方值较大，将 count 加 1，并将 left 向内缩小一个位置。
e. 如果 squareLeft 小于 squareRight，说明 right 指向的数的平方值较大，将 count 加 1，并将 right 向内缩小一个位置。
-
返回 count，即不同平方值的数量。
-
- 时间 && 空间复杂度
03 | 🧢 代码片段
STL法
#include <iostream>
#include <vector>
#include <unordered_set>
int countUniqueSquares(std::vector<int>& arr) {
std::unordered_set<int> squares; // 创建一个空集合来存储平方值的不同取值
for (int num : arr) {
int square = num * num; // 计算平方值
squares.insert(square); // 将平方值添加到集合中
}
return squares.size(); // 返回集合的大小，即不同平方值的数量
}
int main() {
// 测试样例
std::vector<int> arr = {-4, -2, -1, 0, 1, 3, 5};
int result = countUniqueSquares(arr);
std::cout << "(STL法)不同平方值的数量为: " << result << std::endl;
return 0;
}
双指针法
#include <iostream>
#include <vector>
#include <algorithm>
int countUniqueSquares(std::vector<int>& arr) {
// 对数组进行排序，按照绝对值的大小进行排序
std::sort(arr.begin(), arr.end(), [](int a, int b) {
return std::abs(a) < std::abs(b);
});
int count = 0; // 记录不同平方值的数量
int left = 0; // 左指针
int right = arr.size() - 1; // 右指针
while (left <= right) {
if (arr[left] >= 0) {
// 计算平方值，并将右指针往左移动
count++;
right--;
} else if (arr[right] < 0) {
// 计算平方值，并将左指针往右移动
count++;
left++;
} else {
// arr[left] < 0 且 arr[right] >= 0，比较平方值，根据大小移动指针
if (arr[left] * arr[left] != arr[right] * arr[right]) {
count++;
}
left++;
right--;
}
}
return count;
}
int main() {
std::vector<int> arr = {-4, -2, -1, 0, 1, 3, 5};
int result = countUniqueSquares(arr);
std::cout << "(双指针发)不同平方值的数量为: " << result << std::endl;
return 0;
}
