Discuss / Java / 通过洗牌算法shuffle后、通过一次遍历获取List的和、最大值、最小值。使用 等差数列和-List被删除元素后的和=被删除元素。
Back

通过洗牌算法shuffle后、通过一次遍历获取List的和、最大值、最小值。使用 等差数列和-List被删除元素后的和=被删除元素。

Topic source

0

#1 Created at ... [Delete] [Delete and Lock User] 
private static int findMissingNumber2(int start, int end, ArrayList<Integer> list) {

  // 被删除元素后获取List中元素的和、最大值、最小值
  int sum1 = 0;
  int max = start;
  int min = end;

  for (int n : list) {
    sum1 += n;
    if (n > max) max = n;
    if (n < min) min = n;
  }
 
  // 等差数列的和：
  int sum2 = (min + max) * (list.size() + 1) / 2;

  // 特殊情况被拿走的元素是头和尾：
  if (start != min) return start;
  if (end != max) return end;

  // 等差数列的和 - 删除元素后List的和（遍历数组累加） = 缺失的数字
  return sum2 - sum1;
}

0

#2 Created at ... [Delete] [Delete and Lock User]

O(n)（线性时间）：算法的运行时间与输入规模成线性关系，例如遍历一个数组。O(n)（线性时间）：算法的运行时间与输入规模成线性关系，例如遍历一个数组。O(n)（线性时间）：算法的运行时间与输入规模成线性关系，例如遍历一个数组。

0

#3 Created at ... [Delete] [Delete and Lock User]

😓

  • 1

Reply