精华内容
下载资源
问答
  • 给你一个整数数组nums,请你返回所有下标对0 <= i, j < nums.length的floor(nums[i] / nums[j])结果之和。由于答案可能会很大,请你返回答案对109 + 7取余的结果。 函数floor()返回输入数字的整数部分。 ...

    给你一个整数数组 nums ,请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大,请你返回答案对109 + 7 取余 的结果。

    函数 floor() 返回输入数字的整数部分。

     

    示例 1:

    输入:nums = [2,5,9]
    输出:10
    解释:
    floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
    floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
    floor(5 / 2) = 2
    floor(9 / 2) = 4
    floor(9 / 5) = 1
    我们计算每一个数对商向下取整的结果并求和得到 10 。
    示例 2:

    输入:nums = [7,7,7,7,7,7,7]
    输出:49
     

    提示:

    1 <= nums.length <= 105
    1 <= nums[i] <= 105

    思路:首先我们统计出每一种元素在原数组中出现的次数,对于每一个元素x,我们考虑枚举他的倍数,我们假设倍数为d,则d*x<=mx,其中mx是数组中的最大元素,同时假设y=d*x,即y/d=x,而贡献为d的y的范围可以求得为(d+1)*x-1>=y>=d*x,这一块我们可以采用前缀和处理,算法总复杂度为nlogn。

    class Solution {
    
        private static final int mod = 1000000007;
    
        public int sumOfFlooredPairs(int[] nums) {
            int n = nums.length;
            Arrays.sort(nums);
            long ans = 0;
            int mx = 0;
            for (int i = 0; i < n; i++)
                mx = Math.max(mx, nums[i]);
            int[] cnt = new int[mx + 1];
            int[] sum = new int[mx + 1];
            for (int i = 0; i < n; i++)
                cnt[nums[i]]++;
            for (int i = 1; i <= mx; i++)
                sum[i] = sum[i - 1] + cnt[i];
            for (int i = 1; i <= mx; i++) {
                if (cnt[i] == 0)
                    continue;
                for (int j = 1; i * j <= mx; j++) {
                    int upper = Math.min(i * (j + 1) - 1, mx);
                    ans = (ans + (long) cnt[i] * j % mod * (sum[upper] - sum[i * j - 1])) % mod;
                }
            }
            return (int) ans;
        }
    }

     

    展开全文
  • 向下取整数对和 给你一个整数数组 nums ,请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大,请你返回答案对109 + 7 取余 的结果。 函数 floor() 返回...
    1. 向下取整数对和
      给你一个整数数组 nums ,请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大,请你返回答案对109 + 7 取余 的结果。

    函数 floor() 返回输入数字的整数部分。

    示例 1:

    输入:nums = [2,5,9]
    输出:10
    解释:
    floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
    floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
    floor(5 / 2) = 2
    floor(9 / 2) = 4
    floor(9 / 5) = 1
    我们计算每一个数对商向下取整的结果并求和得到 10 。
    示例 2:

    输入:nums = [7,7,7,7,7,7,7]
    输出:49

    提示:

    1 <= nums.length <= 105
    1 <= nums[i] <= 105

    在这里插入图片描述
    先排序,然后二分查找每一项的倍数(当大于最大值的时候结束)所在的最大下标,每次加上数组长度减去下标(一倍的加了一次,两倍的加了两次…),得到最终结果

    class Solution {
        final int NA = 1000000007;
        public int sumOfFlooredPairs(int[] nums) {
            int ans=0;
            Arrays.sort(nums);              //1.排序
            for (int i = 0; i <nums.length ; i++) {
                //2.获取到num[i]的整数倍与最大值比较
                for (int j = 1; nums[i]*j <=nums[nums.length-1] ; j++) {
                    //3.获取到整数倍的最大下标,因为元素的值可重
                    int x = halfArr(nums,nums[i]*j);
                    //4.每次加入每次加上数组长度减去下标,并对1000000007取余
                    ans+=(nums.length-x);
                    ans%=NA;
                }
            }
            return ans;
        }
        //二分查找元素最大下标
        public int halfArr(int[] nums,int x){
            int left = 0;
            int right = nums.length-1;
            while (left<right){
                int privo = (left+right)/2;
                if(nums[privo]>=x){
                    right=privo;
                }else{
                    left=privo+1;
                }
            }
            return left;
        }
    }
    
    展开全文
  • 5212. 向下取整数对和

    2021-05-16 14:43:59
    5212. 向下取整数对和 给你一个整数数组 nums ,请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大,请你返回答案对109 + 7 取余 的结果。 函数 floor()...

    5212. 向下取整数对和

    给你一个整数数组 nums ,请你返回所有下标对 0 <= i, j < nums.lengthfloor(nums[i] / nums[j]) 结果之和。由于答案可能会很大,请你返回答案对109 + 7 取余 的结果。

    函数 floor() 返回输入数字的整数部分。

    示例 1:

    输入:nums = [2,5,9]
    输出:10
    解释:
    floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
    floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
    floor(5 / 2) = 2
    floor(9 / 2) = 4
    floor(9 / 5) = 1
    我们计算每一个数对商向下取整的结果并求和得到 10 。
    

    示例 2:

    输入:nums = [7,7,7,7,7,7,7]
    输出:49
    

    提示:

    • 1 <= nums.length <= 105
    • 1 <= nums[i] <= 105

    思路:

    前缀和。

    c++代码:

    class Solution {
    private:
        const int MOD = 1e9 + 7;
        using LL = long long;
    public:
        int sumOfFlooredPairs(vector<int>& nums) {
            int MAX = *max_element(nums.begin(), nums.end()) + 1;
            //前缀和
            vector<int> cnts(MAX);
            for (int& x : nums) {
                cnts[x]++;
            }
            for (int i = 1; i < MAX; i++) {
                cnts[i] += cnts[i - 1];
            }
    
            LL ans = 0LL;
            for (int i = 1; i < MAX; i++) {
                if (cnts[i]) {
                    for (int j = 1; j * i < MAX; j++) {
                        int l = j * i;//左边界,i 的 j 倍 = 左边界
                        int r = min(MAX - 1, (j + 1) * i - 1);//右边界,检查会不会超出范围
                        LL sum = (cnts[r] - cnts[l - 1]) * j % MOD;//这个范围内的总和
                        ans = (ans + sum * (cnts[i] - cnts[i - 1])) % MOD;//ans + 访问总和 * i 的个数 
                    }
                }
            }
            return ans;
        }
    };
    
    展开全文
  • Leetcode P1862 向下取整数对和 给你一个整数数组 nums ,请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大,请你返回答案对10^9 + 7 取余 的结果。 ...

    Leetcode P1862 向下取整数对和

    给你一个整数数组 nums ,请你返回所有下标对 0 <= i, j < nums.length 的 floor(nums[i] / nums[j]) 结果之和。由于答案可能会很大,请你返回答案对10^9 + 7 取余 的结果。

    函数 floor() 返回输入数字的整数部分。

    示例:

    输入:nums = [2,5,9]
    输出:10
    解释:
    floor(2 / 5) = floor(2 / 9) = floor(5 / 9) = 0
    floor(2 / 2) = floor(5 / 5) = floor(9 / 9) = 1
    floor(5 / 2) = 2
    floor(9 / 2) = 4
    floor(9 / 5) = 1
    我们计算每一个数对商向下取整的结果并求和得到 10

    提示:

    • 1 < = n u m s . l e n g t h < = 1 0 5 1 <= nums.length <= 10^5 1<=nums.length<=105
    • 1 < = n u m s [ i ] < = 1 0 5 1 <= nums[i] <= 10^5 1<=nums[i]<=105

    又是常见的,对于数对如何将O(n2)进行优化的题目。想了一会没想到,本来想排序然后看看能不能把某些具有相同商的数对放在一起处理,结果没想到。

    其实对于这种优化O(n2)的题目,感觉就是可以穷举其中一项i,然后将具有相同结果的所有j进行合并。这里也采用相同的思路,对于分母i,我们穷举得到的商j,注意到这里的数字范围不大,所以i*j需要小于等于 1 0 5 10^5 105。这样穷举下来的时间复杂度就是 1 0 5 ( 1 + 1 2 + 1 3 . . . ) 10^5(1 + \frac{1}{2} + \frac{1}{3}...) 105(1+21+31...),是能过的。代码如下:

    class Solution {
    public:
        int mod = 1e9 + 7;
        int s[100010];
        int sumOfFlooredPairs(vector<int>& nums) {
            int n = nums.size();
            memset(s, 0, sizeof(s));
            for (int num: nums) s[num]++;
            for (int i = 1; i <= 1e5 + 9; i++) s[i] += s[i - 1];
            long long res = 0;
            for (int i = 1; i < 100010; i++) {
                for (int j = 1; j * i < 100010; j++) {
                    int l = j * i, r = min((long long)100009, (long long)(j + 1) * i - 1);
                    long long cnt2 = s[r] - s[l - 1], cnt1 = s[i] - s[i - 1];
                    res = (res + cnt1 * cnt2 * j % mod) % mod;
                }
            }
            return res;
        }
    };
    
    展开全文
  • JS 中的Math方法向上取整、向下取整、保留整数、绝对值、最大值、最小值等 1.只保留整数部分(丢弃小数部分) parseInt(5.1234);// 5 2.向下取整(<= 该数值的最大整数)和parseInt()一样 Math.floor(5....
  • python中如何取整数

    2021-03-18 08:49:00
    这个进位的意思是:-0.5 → -1;0.5 → 1.即正负情况不同,都向着远离0,使得绝对值更大的方向进位向上取整:math.ceil()import mathmath.ceil(-0.5)>>> 0math.ceil(-0.9)>>> 0math.cei...
  • 摘要:这篇JavaScript栏目的“js取整数、取余数的方法”,介绍的技术点是“取余数、取整数、取余、取整、js、方法”,希望对大家开发技术学习和问题解决有帮助。1.丢弃小数部分,保留整数部分parseInt(5/2)2.向上...
  • 2.向下取整。正数:舍弃小数,只要整数部分。负数:有小数,舍弃小数,整数减1Math.floor();3.取绝对值。正数就是本身,负数取反Math.abs();4.四舍五入。正数:第一位小数大于5,则整数加1,反之取整数。负数:第一...
  • JS中数字取整数

    2021-07-21 15:27:51
    一、直接取整 1.parseInt(number) 这大概是取整最常用的方法了,因为parseInt()不是只能处理...注意,parseInt()可以识别各种整数格式(十进制,八进制和十六进制)。 var num1 = parseInt("2015nov"), //2015 num2
  • BigDecimal取整数

    2021-10-18 13:52:15
    * @Description: BigDecimal取整数 * @Param: [args] * @Author: yaohongan * @Date: 2021/10/18 13:47 */ public static void main(String[] args) { // ROUND_UP:非0时,舍弃小数后(整数部分)加1,比如...
  • 1.取整 // 丢弃小数部分,保留整数部分 ...// 向下取整,丢弃小数部分 Math.floor(5/2) // 2 4.四舍五入 // 四舍五入 Math.round(5/2) // 3 5.取余 // 取余(小数也可以) 6%4 // 2 10.23%10 //0.23 ...
  • 【四舍五入取整截取】select round(54.56,0)【向下取整截取】SELECT FLOOR(54.56)【向上取整截取】SELECT CEILING(13.15)--MSSQL取整函数的使用--两个整数相除将截断小数部分select 3/4,4/3,5/3--结果 0,1,1--返回...
  • 似乎每当我将负整数除以正整数时,我都需要将其舍入... 因此,我想知道我是否缺少某些东西,以及您是否有一种"优雅"的方式可以将负除法向下舍入。举例说明所需的行为。例? 好,我需要(-5)/ 3才能产生-2,而不是-1...
  • 1、向下取整: int() >>> a = 14.38 >>> int(a) 14 2、向上取整:ceil() 使用ceil()方法时需要导入math模块,例如 >>> import math >>> math.ceil(3.33) 4 >>> math....
  • (4.0分) 【填空题】数学函数库 math 中,向上取整的函数为 ,向下取整的函数为 。 (4.0分) 【单选题】13.- _____TV do you watch every day?-About two hours. 【单选题】Python 中用于整数除法商的运算符是() (4.0...
  • 本系列文章译自Python之父 Guido van Rossum 的系列博客“The History of Python”。...系列地址:http://blog.kantli.com/theme/11今天又有人问我,为什么 Python 中整数相除是向下取整,而不像 C语言一样靠...
  • python取整数部分的几种方法

    千次阅读 2021-03-06 12:01:57
    python取整数部分的几种方法 1、向下取整:int() >>> a = 14.38 >>> int(a) 14 2、向上取整:ceil() 使用ceil()方法时需要导入math模块,例如 >>> import math >>> math.ceil...
  • 项目经验:做分页时用向上取整方法Math.ceil() this.total = res.data.data.count//总数 this.all = Math.ceil(res.data.data.count / res.data.data.size) //总页数 ...1.丢弃小数部分,保留整数部分 ...
  • C语言有以下几种取整方法:1、直接赋值给整数变量。如:int i = 2.5; 或 i = (int) 2.5;这种方法采用的是舍去小数部分2、C/C++中的整数除法运算符“/”本身就有取整功能(int / int),但是整数除法对负数的取整结果和...
  • 在Javascript的数值运算中,很多时候需要对最后计算结果向下取整,Math.floor是javascript中对计算结果向下取整的函数,它总是将数值向下舍入为最接近的整数。此外Math.ceil()函数则是javascript中向上取整函数,...
  • php -- 取整数

    2021-04-29 06:14:21
    PHP取整数函数常用的四种方法,下面收集了四个函数;经常用到取整的函数,今天小小的总结一下!其实很简单,就是几个函数而已~~主要是:ceil,floor,round,intvalceil — 进一法取整说明float ceil ( float value...
  • SYM是什么意思 sym是什么意思

    千次阅读 2021-04-20 03:16:29
    SYM是什么意思 sym是什么意思SYM是什么意思 sym是什么意思相关问题:匿名网友:函数功能:在MATLAB中,该函数用于创建符号数字、符号变量、符号对象。符号对象的类型是sym,可以通过class(S)来验证,这里S是一个符号...
  • 2.向下取整(<= 该数值的最大整数)和parseInt()一样 Math.floor(5.1234);// 5 3.向上取整(有小数,整数就+1) Math.ceil(5.1234); 4.四舍五入(小数部分) Math.round(5.1234);// 5 Math.round(5.6789);// 6...
  • C语言有以下几种取整方法:1、直接赋值给整数变量。如:int i = 2.5; 或 i = (int) 2.5;这种方法采用的是舍去小数部分。2、C/C++中的整数除法运算符"/"本身就有取整功能(int / int)...3、使用floor函数,向下取整。f...
  • JS如何取整数

    2021-11-05 19:21:06
    1.丢弃小数部分,保留整数部分 parseInt(5/2) 2.向上取整,有小数就整数部分加1 Math.ceil(5/2) 3,四舍五入. Math.round(5/2) 4,向下取整 Math.floor(5/2)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 213,289
精华内容 85,315
关键字:

向下取整数是什么意思