CTF of Z2BNS
0%

统计位数为偶数的数字

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给你一个整数数组 nums，请你返回其中位数为 偶数 的数字的个数。

示例1：

1
2
3
4
5
6
7
8
9
输入：nums = [12,345,2,6,7896]
输出：2
解释：
12 是 2 位数字（位数为偶数） 
345 是 3 位数字（位数为奇数）  
2 是 1 位数字（位数为奇数） 
6 是 1 位数字 位数为奇数） 
7896 是 4 位数字（位数为偶数）  
因此只有 12 和 7896 是位数为偶数的数字

示例2：

1
2
3
4
输入：nums = [555,901,482,1771]
输出：1 
解释： 
只有 1771 是位数为偶数的数字。

提示：

  • 1 <= nums.length <= 500
  • 1 <= nums[i] <= 10^5
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

1、因为1<=nums[i]<=10^5，所以位数为偶数只能有三种情况

  • 6位数，nums[i]等于100000
  • 4位数，0<nums[i]/1000<10
  • 2位数，0<nums[i]/10<10

对这三种情况的数字进行计数即可。

2、另外也可以遍历数组，判断每一个整数的位数

c++代码：(执行用时8ms，击败96.89%，内存消耗10M，击败17.69%）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int result=0;
        for(auto i:nums){
            if(i==100000 || i/1000!=0&&i/1000<10 || i/10!=0&&i/10<10){
                ++result;
            }
        }
        return result;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：枚举 + 字符串
我们枚举数组 nums 中的整数，并依次判断每个整数 x 是否包含偶数个数字。

一种简单的方法是使用语言内置的整数转字符串函数，将 x 转换为字符串后，判断其长度是否为偶数即可。

c++代码：（执行16ms，击败43.91%，内存10M，击败12.53%）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int ans = 0;
        for (int num: nums) {
            if (to_string(num).size() % 2 == 0) {
                ++ans;
            }
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$ 是数组 nums 的长度。这里假设将整数转换为字符串的时间复杂度为 $O(1)$。

  • 空间复杂度：$O(1)$。

方法二：枚举 + 数学
我们也可以使用语言内置的以 10 为底的对数函数 log10() 来得到整数 x 包含的数字个数。

一个包含 k 个数字的整数 x 满足不等式 $10^{k-1} ≤x<10^k$ 。将不等式取对数，得到 $k - 1 \leq \log_{10}(x) < k$，因此我们可以用 $k = \lfloor\log_{10}(x) + 1⌋$得到 x 包含的数字个数 k，其中 $\lfloor a ⌋$表示将 $a$ 进行下取整，例如 $\lfloor 5.2 \rfloor$ = 5⌊5.2⌋=5。

c++代码：（执行20ms，击败16.37%，内存10.4M，击败5.09%）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int ans = 0;
        for (int num: nums) {
            if ((int)(log10(num) + 1) % 2 == 0) {
                ++ans;
            }
        }
        return ans;
    }
};
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

题目多种解法，官方题解第一种即是我思路里的第二种方法，也挺好不错。

------------- THE END! THANKS! -------------