一道Amazon OA题求最优解

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. 
   
7. using namespace std;
   
8. 
   
9. int total_swap(vector<int> &nums) {
   
10.     vector<int> nums2 = nums;
    
11.     sort(nums2.begin(), nums2.end());
    
12.     unordered_map<int, int> position; //{num, index}
    
13. 
    
14.     int n = nums2.size();
    
15.     for (int i = 0; i < n; i++)
    
16.         position[nums2[i]] = i;
    
17. 
    
18.     int ans = 0;
    
19.     int i = 0;
    
20. 
    
21.     while (i < n) {
    
22.         if (position[nums[i]] == i) { //check if nums[i] already in the final position
    
23.             i++;
    
24.             continue;
    
25.         }
    
26. 
    
27.         bool swapped = false;
    
28. 
    
29.         for (int j = i + 1; j < n; j++) {
    
30.             if (nums[i] > nums[j]) {
    
31.                 swap(nums[i], nums[j]);
    
32.                 swapped = true;
    
33.                 ans++;
    
34.                 break;
    
35.             }   
    
36.         }
    
37. 
    
38.         if (swapped == false)
    
39.             i++;
    
40.     }   
    
41. 
    
42.     return ans;
    
43. }
    
44. 
    
45. int main()
    
46. {
    
47.     vector<int> nums;
    
48. 
    
49.     //generate random test case
    
50.     int n = 100000;
    
51.     unordered_set<int> seen;
    
52.     cout << "Generate random test case ..." << endl;
    
53.     while (n > 0) {
    
54.         int num = rand();
    
55.         if (seen.count(num) == 0) {
    
56.             nums.push_back(num);
    
57.             seen.insert(num);
    
58.             n--;
    
59.         }   
    
60.     }
    
61.     cout << "Generate random test case: done" << endl;
    
62. 
    
63.     cout << total_swap(nums) << endl;
    
64.     return 0;
    
65. }
    

复制代码

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

这就是求逆序对个数啊，你搜一下归并排序求逆序对。

蠡口493， reverse pairs

的确是求逆序对个数啊，没反应过来。。。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

这个是伞药吾把