回复: 5
跳转到指定楼层
上一主题 下一主题
收起左侧

一道Amazon OA题求最优解

全局:

2020(4-6月) 码农类General 硕士 全职@amazon - 猎头 - 技术电面  | | Other | 在职跳槽

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 whiteboard 于 2021-2-28 03:46 编辑

OA时间:2/26/2021

输入一个数组nums,长度为10^5,没有重复的数字。不断的做swap,直到数组变成升序排列。返回总共swap的次数。
swap的规则如下:
选定最小的index pair [i, j],且nums >
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
是没有充分利用到“数组里没有重复的数字”这个条件。

大家如果有最优解,可以用我下面test case试一试。

  1. #include <iostream>
  2. #include <vector>
  3. #include <unordered_set>
  4. #include <unordered_map>
  5. #include <algorithm>

  6. using namespace std;

  7. int total_swap(vector<int> &nums) {
  8.     vector<int> nums2 = nums;
  9.     sort(nums2.begin(), nums2.end());
  10.     unordered_map<int, int> position; //{num, index}

  11.     int n = nums2.size();
  12.     for (int i = 0; i < n; i++)
  13.         position[nums2[i]] = i;

  14.     int ans = 0;
  15.     int i = 0;

  16.     while (i < n) {
  17.         if (position[nums[i]] == i) { //check if nums[i] already in the final position
  18.             i++;
  19.             continue;
  20.         }

  21.         bool swapped = false;

  22.         for (int j = i + 1; j < n; j++) {
  23.             if (nums[i] > nums[j]) {
  24.                 swap(nums[i], nums[j]);
  25.                 swapped = true;
  26.                 ans++;
  27.                 break;
  28.             }   
  29.         }

  30.         if (swapped == false)
  31.             i++;
  32.     }   

  33.     return ans;
  34. }

  35. int main()
  36. {
  37.     vector<int> nums;

  38.     //generate random test case
  39.     int n = 100000;
  40.     unordered_set<int> seen;
  41.     cout << "Generate random test case ..." << endl;
  42.     while (n > 0) {
  43.         int num = rand();
  44.         if (seen.count(num) == 0) {
  45.             nums.push_back(num);
  46.             seen.insert(num);
  47.             n--;
  48.         }   
  49.     }
  50.     cout << "Generate random test case: done" << endl;

  51.     cout << total_swap(nums) << endl;
  52.     return 0;
  53. }
复制代码


[/i][/i][/i][/i][/i][/i]

评分

参与人数 1大米 +12 收起 理由
匿名用户-4WGMM + 12

查看全部评分


上一篇:stripe 店面
下一篇:图森 ng 新鲜 OA
🔗
qzane 2021-2-28 04:45:31 | 只看该作者
全局:
这就是求逆序对个数啊,你搜一下归并排序求逆序对。

评分

参与人数 1大米 +1 收起 理由
phonger + 1 赞一个

查看全部评分

回复

使用道具 举报

🔗
dorisH 2021-2-28 06:56:48 | 只看该作者
全局:
蠡口493, reverse pairs
回复

使用道具 举报

🔗
 楼主| whiteboard 2021-2-28 07:54:34 | 只看该作者
全局:
的确是求逆序对个数啊,没反应过来。。。
回复

使用道具 举报

🔗
milanism 2021-3-1 06:34:17 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
回复

使用道具 举报

全局:
这个是伞药吾把
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表