【 NO.1 找出数组排序后的目标下标】

解题思路

签到题，循环判断即可。

代码展示

class Solution {

   public List targetIndices(int[] nums, int target) {

       Arrays.sort(nums);

       List res = new ArrayList<>();

       for (int i = 0; i < nums.length; i++) {

           if (nums[i] == target) {

               res.add(i);

          }

      }

       return res;

  }

}

【 NO.2 半径为 k 的子数组平均值】

解题思路

使用前缀和计算区间和。注意使用 long 类型以避免溢出。

代码展示

class Solution {

   public int[] getAverages(int[] nums, int k) {

       if (k == 0) {

           return nums;

      }

       long[] preSum = new long[nums.length];

       preSum[0] = nums[0];

       for (int i = 1; i < nums.length; i++) {

           preSum[i] = preSum[i - 1] + nums[i];

      }

       int[] res = new int[nums.length];

       Arrays.fill(res, -1);

       for (int i = k; i + k < nums.length; i++) {

           long sum = 0;

           if (i - k == 0) {

               sum = preSum[i + k];

          } else {

               sum = preSum[i + k] - preSum[i - k - 1];

          }

           res[i] = (int) (sum / (long) (k * 2 + 1));

      }

       return res;

  }

}

【 NO.3 从数组中移除最大值和最小值】

解题思路

贪心，按照最小的花费移除即可。详见注释。

代码展示

class Solution {

   public int minimumDeletions(int[] nums) {

       if (nums.length <= 2) {

           return nums.length;

      }

       // 找出最大值和最小值的下标，由于 len > 2 且元素互不相同，所以最终 max 一定不等于 min

       int min = 0, max = 0;

       for (int i = 1; i < nums.length; i++) {

           if (nums[i] < nums[min]) {

               min = i;

          }

           if (nums[i] > nums[max]) {

               max = i;

          }

      }

       // 要移除的元素下标为 max 和 min

       // 此时我们只关心下标，谁是最大值谁是最小值不重要

       // 为了方便处理，令 min 为较小的下标

       if (min > max) {

           int t = min;

           min = max;

           max = t;

      }

       int res = 0;

       int left = 0, right = nums.length - 1;

       if (min - left + 1 < right - max + 1) {

           res += min - left + 1; // 贪心，移除 min 需要更少的操作，先移除 min

           left = min + 1;

           res += Math.min(max - left + 1, right - max + 1); // 然后再移除 max

      } else {

           res += right - max + 1;

           right = max - 1;

           res += Math.min(min - left + 1, right - min + 1);

      }

       return res;

  }

}

【 NO.4 找出知晓秘密的所有专家】

解题思路

并查集，详见注释。

代码展示

class Solution {

   public List findAllPeople(int n, int[][] meetings, int firstPerson) {

       // 按照时间点将会议分组

       TreeMap<Integer, List<int[]>> orderedMeetings = new TreeMap<>();

       for (var m : meetings) {

           if (!orderedMeetings.containsKey(m[2])) {

               orderedMeetings.put(m[2], new ArrayList<>());

          }

           orderedMeetings.get(m[2]).add(m);

      }

       boolean[] known = new boolean[n];

       known[0] = known[firstPerson] = true;

       while (!orderedMeetings.isEmpty()) {

           // 按照时间顺序处理每一波会议

           var entry = orderedMeetings.pollFirstEntry();

           var curMeetings = entry.getValue();

           // 使用并查集维护当前时间点发生的所有会议中，有关联的人

           UnionFind uf = new UnionFind(n);

           for (var m : curMeetings) {

               uf.merge(m[0], m[1]);

          }

           // 枚举所有会议

           // 若会议参加人 m[0] 或 m[1] 知晓秘密

           // 则把他们所在的根节点也标记为知晓秘密

           for (var m : curMeetings) {

               if (known[m[0]] || known[m[1]]) {

                   known[uf.find(m[0])] = true;

                   known[uf.find(m[1])] = true;

              }

          }

           // 枚举所有的参会人，若他们所在的根节点知晓秘密，则把他们也标记为知晓秘密

           for (var m : curMeetings) {

               if (known[uf.find(m[0])] || known[uf.find(m[1])]) {

                   known[m[0]] = true;

                   known[m[1]] = true;

              }

          }

      }

       List res = new ArrayList<>();

       for (int i = 0; i < n; i++) {

           if (known[i]) {

               res.add(i);

          }

      }

       return res;

  }

}

class UnionFind {

   public UnionFind(int size) {

       f = new int[size];

       Arrays.fill(f, -1);

  }

   public int find(int x) {

       if (f[x] < 0)

           return x;

       return f[x] = find(f[x]);

  }

   public boolean merge(int a, int b) {

       int fa = find(a);

       int fb = find(b);

       if (fa == fb)

           return false;

       f[fa] = fb;

       return true;

  }

   public Map<Integer, List> sets() {

       Map<Integer, List> res = new HashMap<>();

       for (int i = 0; i < f.length; i++) {

           int fi = find(i);

           if (!res.containsKey(fi)) {

               res.put(fi, new ArrayList<>());

          }

           res.get(fi).add(i);

      }

       return res;

  }

   private int[] f;

}