范围内没有重复数字的总数  


难度级别 中等
经常问 ol石 事实集 空气质量
数学 数字位数

系统会为您提供一系列数字(开始,结束)。 给定的任务是找出一个范围内没有重复数字的总数。

使用案列  

输入:

10 50

输出:

37

说明:

10没有重复的数字。 11有一个重复的数字。 12没有重复的数字。 而22、33具有重复数字。 因此,当我们找到没有重复数字的数字时,我们会将其计入结果。

范围内没有重复数字的总数Pin

算法  

  1. 声明一个 和一个向量。
  2. 将0和1推到向量中,找出所有等于10的因子,然后将余数存储到集合中。 如果集合已经包含该数字,则返回0,否则返回1。
  3. 获取该号码并将其添加到 向量.
  4. 对于每个查询,返回vector [end]和vector [start]的差。

范围内无重复数字的总数的说明  

我们给出了一个范围。 我们已要求找出给定范围内的数字总数,数字本身中没有重复的数字。 为此,我们将使用收集框架。 我们将使用集合和向量。 集合用于存储不常见的因子或数字的余数,向量用于存储从集合中滤除的数字。 我们知道,只有少数几位数字没有重复,例如10到1,就没有重复数字。 从10到11和10到21,有两个重复的数字分别为30和11,这是相同的。

参见
计算数组中存在其产品的对

我们将数字0和1加到向量中,从值2到给定值,无论它是多少。 如上所述,获得一个因数或余数为10的数字。 如果集合已经包含该数字作为余数,我们将获得这些余数并将其添加到集合中。 返回0,否则将该余数添加到集合中。 因为它将是一个新数字或余数,然后返回1。继续遍历直到值变为0。在这里,我们将从0或1之类的数字中获取数字,并将其与通过向量获取的数字相加,然后将计数推入向量本身。

对于每个给定的查询,我们将在向量中的右侧位置返回数字差,这意味着右侧范围,而在左侧位置的数字意味着返回矢量中左侧范围的数字。 我们将退还这笔差额,这将是必需的答案。

实施   

范围内无重复数字的总数的C ++程序

#include <iostream>
#include<vector>
#include<unordered_set>

using namespace std;

int MAX = 1000;

vector<int> numbers = {0};

int getRepeatedNumber(int n)
{

    unordered_set<int> SET;
    int rem;

    while (n != 0)
    {
        rem = n % 10;
        if (SET.find(rem) != SET.end())
            return 0;

        SET.insert(rem);
        n = n / 10;
    }
    return 1;
}

void buildSetOfNumbers(int MAX)
{

    numbers.push_back(getRepeatedNumber(1));

    for (int i = 2; i < MAX + 1; i++)
        numbers.push_back(getRepeatedNumber(i) + numbers[i-1]);
}

int getNumber(int left,int right)
{
    return numbers[right] - numbers[left-1];
}
int main()
{
    int Left = 10, Right = 50;
    buildSetOfNumbers(MAX);

    cout << getNumber(Left, Right) << endl;

    return 0;
}
37

范围内无重复数字的总数的Java程序

import java.util.Vector;
import java.util.HashSet;

class repeatedDigits
{
    private static int MAX = 100;
    private static Vector<Integer> numbers = new Vector<>();
    
    static int getRepeatedNumber(int n)
    {
        HashSet<Integer> set = new HashSet<>();
        int rem;

        while (n != 0)
        {
            rem = n % 10;

            if (set.contains(rem))
                return 0;

            set.add(rem);
            n /= 10;
        }
        return 1;
    }
    
    static void buildSetOfNumbers()
    {
        numbers.add(0);
        numbers.add(getRepeatedNumber(1));

        for (int i = 2; i < MAX + 1; i++)
            numbers.add(getRepeatedNumber(i) + numbers.elementAt(i - 1));
    }
    
    static int getNumber(int left, int right)
    {
        return numbers.elementAt(right) - numbers.elementAt(left - 1);
    }
    
    public static void main(String[] args)
    {
        int Left = 10, Right = 50;

        buildSetOfNumbers();
        System.out.println(getNumber(Left, Right));
    }
}
37

复杂度分析  

时间复杂度

O(1) 因为不需要额外的时间。

参见
最大产品子阵列

空间复杂度

O(N) 哪里 “ n” 是数组中元素的数量。