lintcode-248-统计比给定整数小的数的个数

248-统计比给定整数小的数的个数

给定一个整数数组（下标由 0 到 n-1，其中 n 表示数组的规模，数值范围由 0 到 10000），以及一个查询列表。对于每一个查询，将会给你一个整数，请你返回该数组中小于给定整数的元素的数量。

注意事项

在做此题前，最好先完成线段树的构造 and 线段树查询 II 这两道题目。

样例

对于数组 [1,2,7,8,5] ，查询 [1,8,5]，返回 [0,4,2]

挑战

否用一下三种方法完成以上题目。

仅用循环方法

分类搜索和二进制搜索

构建线段树和搜索

标签

LintCode 版权所有二分法线段树

方法一（循环 + 二分查找）

首先对 A 排序，然后以 queries 的每个元素为 target ，用二分查找寻找 target 在 A 的下标，下标值即 A 中小于给定 target 的元素的数量

code

class Solution {

public:

    /*

     * @param A: An integer array

     * @param queries: The query list

     * @return: The number of element in the array that are smaller that the given integer

     */

    vector<int> countOfSmallerNumber(vector<int> A, vector<int> queries) {

        // write your code here

        int sizeA = A.size(), sizeQ = queries.size();

        if (sizeA <= 0 && sizeQ > 0) {

            return vector<int>(sizeQ, 0);

        }

        if (sizeA <= 0 && sizeQ <= 0) {

            return vector<int>();

        }

        vector<int> result;

        sort(A.begin(), A.end());

        for (int target : queries) {

            int count = lower_bound(A.begin(), A.end(), target) - A.begin();

            result.push_back(count);

        }

        return result;

    }

};

方法二（线段树）

使用线段树，代码结果是 MLE（超出内存），不过还是简单介绍一下

使用线段树，线段树的额外属性 count 为 A 中 start 到 end 中小于 target 的元素个数，之后以 queries 的每个元素为 target，分别建立线段树

线段树自底而上构建，参考lintcode-439-线段树的构造 II

code

/**

* Definition of SegmentTreeNode:

*/

class mySegmentTreeNode {

public:

    int start, end, count;

    mySegmentTreeNode *left, *right;

    mySegmentTreeNode(int start, int end, int max) {

        this->start = start;

        this->end = end;

        this->count = count;

        this->left = this->right = NULL;

    }

};

class Solution {

public:

    /*

     * @param A: An integer array

     * @param queries: The query list

     * @return: The number of element in the array that are smaller that the given integer

     */

    vector<int> countOfSmallerNumber(vector<int> A, vector<int> queries) {

        // write your code here

        int sizeA = A.size(), sizeQ = queries.size();

        if (sizeA <= 0 && sizeQ > 0) {

            return vector<int>(sizeQ, 0);

        }

        if (sizeA <= 0 && sizeQ <= 0) {

            return vector<int>();

        }

        vector<int> result;

        for (int target : queries) {

            mySegmentTreeNode *root = build(0, sizeA - 1, A, target);

            result.push_back(root->count);

        }

        return result;

    }

    mySegmentTreeNode * build(int start, int end, vector<int> &nums, int target) {

        // write your code here

        if (start > end) {

            return nullptr;

        }

        mySegmentTreeNode *root = new mySegmentTreeNode(start, end, 0);

        if (start != end) {

            root->left = build(start, (start + end) / 2, nums, target);

            root->right = build((start + end) / 2 + 1, end, nums, target);

            root->count = root->left->count + root->right->count;

            delete  root->left;            // 减小内存占用

            delete  root->right;

        }

        else {

            if (target > nums[start]) {

                root->count = 1;

            }

            else {

                root->count = 0;

            }

        }

        return root;

    }

};

巴特西

lintcode-248-统计比给定整数小的数的个数

248-统计比给定整数小的数的个数

注意事项

样例

挑战

标签

方法一（循环 + 二分查找）

code

方法二（线段树）

code

最新文章

热门文章