亚麻SDE2-OA

Q1: 妖灵丝妖

Q2: There is an unsorted array. The requir

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

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

ge 1<=len(arr0<=10^9.

求大米

请问lz是105min coding + 20 min survey 的OA吗

utm 发表于 2021-7-21 18:01
请问lz是105min coding + 20 min survey 的OA吗

是啊 紫薯紫薯紫薯紫薯

Q2  用 merge sort做嗎? 這題好難..

范晓康 发表于 2021-7-22 01:18
Q2  用 merge sort做嗎? 這題好難..

我网上找到了solution，但是看不懂

1. void update(int idx, std::vector<int>&tree, int n) {
   
2.         while (idx <= n) {
   
3.                 tree[idx] ++;
   
4.                 auto t = idx&-idx;
   
5.                 idx += t;
   
6.         }
   
7. }
   
8. 
   
9. int query(int idx, std::vector<int>&tree) {
   
10.         int ans = 0;
    
11.         while (idx != 0) {
    
12.                 ans += tree[idx];
    
13.                 idx -= (idx&-idx);
    
14.         }
    
15.         return ans;
    
16. }
    
17. //O(n*logn)
    
18. int number_of_swaps_to_sort(std::vector<int> nums) {
    
19.         int n = nums.size();
    
20.         //It works if numbers are unique
    
21.         //first compress the values keeping the order,  example [10, 4, 8 , 5] -> [4,1,3,2]
    
22.         std::vector<int>aux = nums;
    
23.         sort(aux.begin(), aux.end());
    
24.         std::unordered_map<int, int>ranking;
    
25.         for (int i = 0; i < n; i++) ranking[aux[i]] = i + 1;
    
26.         for (int i = 0; i < n; i++) nums[i] = ranking[nums[i]];
    
27. 
    
28.         //[4, 1,3 ,2]  for each value, count number of elements on right side which are smaller than it.
    
29.         //we can use binary indexed trees
    
30.         std::vector<int>tree(n + 1, 0);
    
31.         int ans = 0;
    
32.         for (int i = n - 1; i >= 0; i--) {
    
33.                 update(nums[i], tree, n);
    
34.                 ans += query(nums[i] - 1, tree);
    
35.         }
    
36. 
    
37.         return ans;
    
38. }

复制代码

楼主请问是找到最小swap次数吗？有没有只能swap相邻元素的限制呀？

LuckyBiu 发表于 2021-7-25 02:07
楼主请问是找到最小swap次数吗？有没有只能swap相邻元素的限制呀？

对，只能swap相邻的