• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

C++pair用法

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

刷leecode有这么一道题:

给定两个大小相等的数组 A 和 B,A 相对于 B 的优势可以用满足 A[i] > B[i] 的索引 i 的数目来描述。

返回 A 的任意排列,使其相对于 B 的优势最大化。

我第一次想的是枚举法,然后超时了。

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        int max = 0;
        vector<int> maxVector;
        maxVector.insert(maxVector.begin(), A.begin(), A.end());
        sort(A.begin(), A.end());
        do
        {
            int count = 0;
            for(int i = 0; i < A.size(); i ++)
            {
                if(A[i] > B[i] ) count++;
            }
            if(count > max)
            {
                max = count;
                maxVector.clear();
                maxVector.insert(maxVector.begin(), A.begin(), A.end());            
            }
        } while(next_permutation(A.begin(), A.end()));
        return maxVector;
    }
};

 后来想了想。换了一种方法做。通过用例了。

1.首先两个数组进行排序,如果数组A[i] > B[j];,用pair存储B数组未排序的索引 可以认为B[j]之前的索引数组都是小于等于A[i].

2. 则对数组A遍历,找到满足A[i]>B[j]的值,取代结果数组B中原先索引值。

代码如下:

class Solution {
public:
    vector<int> advantageCount(vector<int>& A, vector<int>& B) {
        vector<pair<int, int> > b_matrix;
        vector<int> result;  //存储结果索引值
        result.resize(B.size());
        int flag = -1;
        for(int i = 0; i < B.size(); i++)
        {
            b_matrix.push_back(make_pair(B[i],i));
        }
        sort(A.begin(), A.end());
        sort(b_matrix.begin(), b_matrix.end());
        int j = A.size()-1;
        int k = A.size()-1;
        int i = 0;
        while(j>=0)
        {
            if(A[k] > b_matrix[j].first) {
                result[b_matrix[j].second] = A[k];
                k--;
                j--;
            } else {
                result[b_matrix[j].second] = A[i];
                i++;
                j--;
            }
            
        }
         
        return result;
    }
};
/*********example ******

A[k]:          1 2  2 4 6
b_matrix[j]:0 2 2 4 5
6取代5原先的索引,  
4取代2原先的索引,
2取代0原来的索引值。
其他位置则随意
****************/

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
c#BackgroundWorker组件介绍(属性、方法、事件)发布时间:2022-07-14
下一篇:
C++计算几何库发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap