亚麻八月OA SDEII

八月初拿到的oa。SDEII, 90min 2道题。第二题只做出了暴力解没做出最优解，以为能混过去结果没

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

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

rong>
第二题少加了一张n的范围的图，经评论提醒加在评论区了

匿名用户 发表于 2022-09-05 17:41:35
n范围是 1000 还是10000 ？很关键的信息 …

3000。补了原题的图。有用的话记得加米哦

第二题 数组长度范围是多少

匿名用户 发表于 2022-09-05 17:39:56
第二题 数组长度范围是多少

n范围是 1000 还是10000 ？很关键的信息 …

第二题用滑动窗口遍历整个rank数组，同时维护一个sorted_list，里面维护的是排好序的当前的滑动窗口中的元素。每次向右移动的时候，用二分查找更新这个sorted_list，这样时间复杂度是O(logn)，总的时间复杂度是O(n^2logn)

补充内容 (2022-09-06 13:46 +08:00):
好像不对，修改数组时间复杂度是o（n），那就是o（n^3）

hhjimhhj 发表于 2022-09-05 19:34:17
第二题用滑动窗口遍历整个rank数组，同时维护一个sorted_list，里面维护的是排好序的当前的滑动窗口中的元素。每次向右移动的时候，用二分查找更新这个sorted_list，这样时间复杂度是O(

维护数组复杂度太高了 应该维护区间。 这题核心就是算有多少个不连续的区间

匿名用户 发表于 2022-9-6 02:22
维护数组复杂度太高了 应该维护区间。 这题核心就是算有多少个不连续的区间

只维护区间的左右端点吗，那如果一个区间是1，4，5，一个是1，3，5结果是不一样的啊，不太清楚什么意思

hhjimhhj 发表于 2022-09-06 16:12:34
只维护区间的左右端点吗，那如果一个区间是1，4，5，一个是1，3，5结果是不一样的啊，不太清楚什么意思

是应该不一样的吧

1，4，5 的imblance是1。

1，3，5的imbalance是2

1. import java.util.HashSet;
   
2. import java.util.Set;
   
3. 
   
4. class Solution {
   
5.     public int findTotalImbalance(int[] rank) {
   
6.         int res = 0;
   
7.         int n = rank.length;
   
8.         for (int i = 0; i < n; i++) {
   
9.             int count = 0;
   
10.             Set<Integer> set = new HashSet<>();
    
11.             for (int j = i; j < n; j++) {
    
12.                 count++;
    
13.                 if (set.contains(rank[j] + 1)) {
    
14.                     count--;
    
15.                 }
    
16.                 if (set.contains(rank[j] - 1)) {
    
17.                     count--;
    
18.                 }
    
19.                 set.add(rank[j]);
    
20.                 if (count > 1) {
    
21.                     res++;
    
22.                 }
    
23.             }
    
24.         }
    
25.         return res;
    
26.     }
    
27. 
    
28.     public static void main(String[] args) {
    
29.         Solution s = new Solution();
    
30.         System.out.println(s.findTotalImbalance(new int[]{4, 1, 3, 2}) == 3);
    
31.     }
    
32. }

复制代码

这样对吗？不记得在哪个帖子看到的解法。O(n^2)。终于看到这道题的数据范围了。