Question

2659. Make Array Empty

中文文档

Description

You are given an integer array nums containing distinct numbers, and you can perform the following operations until the array is empty:

• If the first element has the smallest value, remove it
• Otherwise, put the first element at the end of the array.

Return _an integer denoting the number of operations it takes to make _nums_ empty._

 

Example 1:

Input: nums = [3,4,-1]
Output: 5

Operation	Array
1	[4, -1, 3]
2	[-1, 3, 4]
3	[3, 4]
4	[4]
5	[]

Example 2:

Input: nums = [1,2,4,3]
Output: 5

Operation	Array
1	[2, 4, 3]
2	[4, 3]
3	[3, 4]
4	[4]
5	[]

Example 3:

Input: nums = [1,2,3]
Output: 3

Operation	Array
1	[2, 3]
2	[3]
3	[]

 

Constraints:

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• All values in nums are distinct.

Solutions

Solution 1: Hash Table + Sorting + Fenwick Tree

First, we use a hash table $pos$ to record the position of each element in array $nums$. Then, we sort array $nums$. The initial answer is the position of the minimum element in array $nums$ plus 1, which is $ans = pos[nums[0]] + 1$.

Next, we traverse the sorted array $nums$, the indexes of the two adjacent elements $a$ and $b$ are $i = pos[a]$, $j = pos[b]$. The number of operations needed to move the second element $b$ to the first position of the array and delete it is equal to the interval between the two indexes, minus the number of indexes deleted between the two indexes, and add the number of operations to the answer. We can use a Fenwick tree or an ordered list to maintain the deleted indexes between two indexes, so that we can find the number of deleted indexes between two indexes in $O(\log n)$ time. Note that if $i \gt j$, then we need to increase $n - k$ operations, where $k$ is the current position.

After the traversal is over, return the number of operations $ans$.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Where $n$ is the length of array $nums$.

from sortedcontainers import SortedList


class Solution:
  def countOperationsToEmptyArray(self, nums: List[int]) -> int:
    pos = {x: i for i, x in enumerate(nums)}
    nums.sort()
    sl = SortedList()
    ans = pos[nums[0]] + 1
    n = len(nums)
    for k, (a, b) in enumerate(pairwise(nums)):
      i, j = pos[a], pos[b]
      d = j - i - sl.bisect(j) + sl.bisect(i)
      ans += d + (n - k) * int(i > j)
      sl.add(i)
    return ans

class BinaryIndexedTree {
  private int n;
  private int[] c;

  public BinaryIndexedTree(int n) {
    this.n = n;
    c = new int[n + 1];
  }

  public void update(int x, int delta) {
    while (x <= n) {
      c[x] += delta;
      x += x & -x;
    }
  }

  public int query(int x) {
    int s = 0;
    while (x > 0) {
      s += c[x];
      x -= x & -x;
    }
    return s;
  }
}

class Solution {
  public long countOperationsToEmptyArray(int[] nums) {
    int n = nums.length;
    Map<Integer, Integer> pos = new HashMap<>();
    for (int i = 0; i < n; ++i) {
      pos.put(nums[i], i);
    }
    Arrays.sort(nums);
    long ans = pos.get(nums[0]) + 1;
    BinaryIndexedTree tree = new BinaryIndexedTree(n);
    for (int k = 0; k < n - 1; ++k) {
      int i = pos.get(nums[k]), j = pos.get(nums[k + 1]);
      long d = j - i - (tree.query(j + 1) - tree.query(i + 1));
      ans += d + (n - k) * (i > j ? 1 : 0);
      tree.update(i + 1, 1);
    }
    return ans;
  }
}

class BinaryIndexedTree {
public:
  BinaryIndexedTree(int _n)
    : n(_n)
    , c(_n + 1) {}

  void update(int x, int delta) {
    while (x <= n) {
      c[x] += delta;
      x += x & -x;
    }
  }

  int query(int x) {
    int s = 0;
    while (x) {
      s += c[x];
      x -= x & -x;
    }
    return s;
  }

private:
  int n;
  vector<int> c;
};

class Solution {
public:
  long long countOperationsToEmptyArray(vector<int>& nums) {
    unordered_map<int, int> pos;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      pos[nums[i]] = i;
    }
    sort(nums.begin(), nums.end());
    BinaryIndexedTree tree(n);
    long long ans = pos[nums[0]] + 1;
    for (int k = 0; k < n - 1; ++k) {
      int i = pos[nums[k]], j = pos[nums[k + 1]];
      long long d = j - i - (tree.query(j + 1) - tree.query(i + 1));
      ans += d + (n - k) * int(i > j);
      tree.update(i + 1, 1);
    }
    return ans;
  }
};

type BinaryIndexedTree struct {
  n int
  c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
  c := make([]int, n+1)
  return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) update(x, delta int) {
  for x <= this.n {
    this.c[x] += delta
    x += x & -x
  }
}

func (this *BinaryIndexedTree) query(x int) int {
  s := 0
  for x > 0 {
    s += this.c[x]
    x -= x & -x
  }
  return s
}

func countOperationsToEmptyArray(nums []int) int64 {
  n := len(nums)
  pos := map[int]int{}
  for i, x := range nums {
    pos[x] = i
  }
  sort.Ints(nums)
  tree := newBinaryIndexedTree(n)
  ans := pos[nums[0]] + 1
  for k := 0; k < n-1; k++ {
    i, j := pos[nums[k]], pos[nums[k+1]]
    d := j - i - (tree.query(j+1) - tree.query(i+1))
    if i > j {
      d += n - k
    }
    ans += d
    tree.update(i+1, 1)
  }
  return int64(ans)
}

class BinaryIndexedTree {
  private n: number;
  private c: number[];

  constructor(n: number) {
    this.n = n;
    this.c = Array(n + 1).fill(0);
  }

  public update(x: number, v: number): void {
    while (x <= this.n) {
      this.c[x] += v;
      x += x & -x;
    }
  }

  public query(x: number): number {
    let s = 0;
    while (x > 0) {
      s += this.c[x];
      x -= x & -x;
    }
    return s;
  }
}

function countOperationsToEmptyArray(nums: number[]): number {
  const pos: Map<number, number> = new Map();
  const n = nums.length;
  for (let i = 0; i < n; ++i) {
    pos.set(nums[i], i);
  }
  nums.sort((a, b) => a - b);
  const tree = new BinaryIndexedTree(n);
  let ans = pos.get(nums[0])! + 1;
  for (let k = 0; k < n - 1; ++k) {
    const i = pos.get(nums[k])!;
    const j = pos.get(nums[k + 1])!;
    let d = j - i - (tree.query(j + 1) - tree.query(i + 1));
    if (i > j) {
      d += n - k;
    }
    ans += d;
    tree.update(i + 1, 1);
  }
  return ans;
}

Solution 2

class BinaryIndexedTree:
  def __init__(self, n):
    self.n = n
    self.c = [0] * (n + 1)

  def update(self, x, delta):
    while x <= self.n:
      self.c[x] += delta
      x += x & -x

  def query(self, x):
    s = 0
    while x:
      s += self.c[x]
      x -= x & -x
    return s


class Solution:
  def countOperationsToEmptyArray(self, nums: List[int]) -> int:
    pos = {x: i for i, x in enumerate(nums)}
    nums.sort()
    ans = pos[nums[0]] + 1
    n = len(nums)
    tree = BinaryIndexedTree(n)
    for k, (a, b) in enumerate(pairwise(nums)):
      i, j = pos[a], pos[b]
      d = j - i - tree.query(j + 1) + tree.query(i + 1)
      ans += d + (n - k) * int(i > j)
      tree.update(i + 1, 1)
    return ans