2023-06-20：给定一个长度为 N 的数组 arr，arr[i] 表示宝石的价值你在某天遇到 X 价值的宝石， X 价值如果是所有剩余宝石价值中的最小值，你会将该宝石送人 X 价值如果不是所有剩余宝石价值中的

作者：福大大架构师每日一题

2023-06-20
北京
本文字数：5890 字
阅读完需：约 19 分钟

2023-06-20：给定一个长度为 N 的数组 arr，arr[i]表示宝石的价值

你在某天遇到 X 价值的宝石，

X 价值如果是所有剩余宝石价值中的最小值，你会将该宝石送人

X 价值如果不是所有剩余宝石价值中的最小值，你会将该宝石放到所有宝石的最后

返回把宝石都送人需要多少天

比如 arr = [3,1,4,3,1,2]

在第 1 天，你遇到了价值 3 的宝石，但是 3 并不是所有剩余宝石的价值最小值

所以你把 3 放在了所有宝石的最后，arr = [1,4,3,1,2,3]

在第 2 天，你遇到了价值 1 的宝石，1 是所有剩余宝石的价值最小值

所以你把价值 1 的宝石送人，arr = [4,3,1,2,3]

在第 3 天，你把价值 4 的宝石放到最后，arr = [3,1,2,3,4]

在第 4 天，你把价值 3 的宝石放到最后，arr = [1,2,3,4,3]

在第 5 天，你送出了价值 1 的宝石，arr = [2,3,4,3]

在第 6 天，你送出了价值 2 的宝石，arr = [3,4,3]

在第 7 天，你送出了价值 3 的宝石，arr = [4,3]

在第 8 天，你把价值 4 的宝石放到最后，arr = [3,4]

在第 9 天，你送出了价值 3 的宝石，arr = [4]

在第 10 天，你送出了价值 4 的宝石，宝石已经没有了。

所以返回 10。

1 <= N <= 10 的 5 次方，

1 <= 宝石价值 <= 10 的 9 次方。

来自 TikTok 美国笔试。

答案 2023-06-20：

1.第一个方法(days1)使用了暴力的方式，通过遍历数组并移动宝石来模拟每一天的操作，直到所有宝石都被送出。时间复杂度较高。

2.第二个方法(days2)使用了更高效的算法。首先构建了一个支持查询累加和和最小值的数据结构（IndexTree 和 SegmentTree）。然后利用这些数据结构来计算送出所有宝石需要的天数。具体步骤如下：

2.1.初始化累加和数据结构(it)和最小值数据结构(st)。

2.2.设定起始位置(start)为 1，找到剩余宝石中的最小值(find)。

2.3.计算从起始位置到最小值之间的宝石总数(daysCount)。

2.4.将最小值送出，更新累加和数据结构(it)和最小值数据结构(st)。

2.5.更新起始位置(start)为最小值。

2.6.重复上述步骤直到所有宝石都被送出。

2.7.返回送出宝石所需的天数。

时间复杂度和空间复杂度如下：

方法 1（days1）：

时间复杂度： $O (N^{2})$ ，其中 N 是宝石数组的长度。需要遍历数组 N 次，并且在每次操作中需要移动宝石，移动的次数也达到了 N 次。
空间复杂度：O(N)，需要额外的存储空间来存储宝石数组。

方法 2（days2）：

时间复杂度： $O (N * (l o g N)^{2})$ ，其中 N 是宝石数组的长度。构建 IndexTree 和 SegmentTree 所需的时间复杂度为 O(N * logN)。每次查询最小值的时间复杂度为 O(logN)，总共进行 N 次查询。因此，总的时间复杂度为 $O (N * (l o g N)^{2})$ 。
空间复杂度：O(N)，需要额外的存储空间来构建 IndexTree 和 SegmentTree。

综上所述，方法 1 的时间复杂度为 $O (N^{2})$ ，方法 2 的时间复杂度为 $O (N * (l o g N)^{2})$ 。在时间复杂度上，方法 2 优于方法 1。方法 1 的空间复杂度为 O(N)，方法 2 的空间复杂度为 O(N)。在空间复杂度上，两种方法相同。

go 完整代码如下：

package main
import (  "fmt"  "math"  "math/rand"  "time")
// 暴力方法// 为了验证func days1(diamonds []int) int {  arr := make([]int, len(diamonds))  copy(arr, diamonds)  ans := 0  for len(arr) > 0 {    ans++    deal(&arr)  }  return ans}
// 暴力方法// 为了验证func deal(arr *[]int) {  head := (*arr)[0]  *arr = (*arr)[1:]  min := head  for _, num := range *arr {    min = int(math.Min(float64(min), float64(num)))  }  if head > min {    *arr = append(*arr, head)  }}
// 正式方法// 时间复杂度O(N * (logN)的平方)func days2(diamonds []int) int {  // n : 位置  n := len(diamonds)  // 1 ~ n : 1  it := NewIndexTree(n)  //  7 6 2...  //  1 2 3....  st := NewSegmentTree(diamonds)  days := 0  find, start := 1, 1  for it.SumRange(1, n) != 0 {    // start ..... find(后续....最小值，最左的位置)    find = findMin(st, start, n)    days += daysCount(it, start, find, n)    //  1    // find    it.Add(find, -1)    st.Update(find, math.MaxInt32)    start = find  }  return days}
func findMin(st *SegmentTree, start, n int) int {  // start....n 左部分  1 ~ start-1 右  var l, r, min = n, 1, st.Min(1, n)  if st.Min(start, n) == min {    l = start    r = n  } else {    l = 1    r = start - 1  }  var m, ans = -1, -1  for l <= r {    m = (l + r) / 2    if st.Min(l, m) == min {      ans = m      r = m - 1    } else {      l = m + 1    }  }  return ans}
func daysCount(it *IndexTree, start, find, n int) int {  if start <= find {    return it.SumRange(start, find)  } else {    return it.SumRange(start, n) + it.SumRange(1, find)  }}
// 支持查询累加和type IndexTree struct {  tree []int  n    int}
func NewIndexTree(size int) *IndexTree {  it := &IndexTree{    tree: make([]int, size+1),    n:    size,  }  for i := 1; i <= size; i++ {    it.Add(i, 1)  }  return it}
func (it *IndexTree) Sum(i int) int {  ret := 0  for i > 0 {    ret += it.tree[i]    i -= i & -i  }  return ret}
func (it *IndexTree) SumRange(l, r int) int {  return it.Sum(r) - it.Sum(l-1)}
func (it *IndexTree) Add(i, d int) {  for i <= it.n {    it.tree[i] += d    i += i & -i  }}
// 支持查询最小值type SegmentTree struct {  n   int  min []int}
func NewSegmentTree(arr []int) *SegmentTree {  n := len(arr)  st := &SegmentTree{    n:   n,    min: make([]int, (n+1)<<2),  }  for i := 1; i <= n; i++ {    st.Update(i, arr[i-1])  }  return st}
func (st *SegmentTree) Update(i, v int) {  st.update(i, i, v, 1, st.n, 1)}
func (st *SegmentTree) update(L, R, C, l, r, rt int) {  if L <= l && r <= R {    st.min[rt] = C    return  }  mid := (l + r) >> 1  if L <= mid {    st.update(L, R, C, l, mid, rt<<1)  }  if R > mid {    st.update(L, R, C, mid+1, r, rt<<1|1)  }  st.pushUp(rt)}
func (st *SegmentTree) pushUp(rt int) {  st.min[rt] = int(math.Min(float64(st.min[rt<<1]), float64(st.min[rt<<1|1])))}
func (st *SegmentTree) Min(l, r int) int {  return st.minQuery(l, r, 1, st.n, 1)}
func (st *SegmentTree) minQuery(L, R, l, r, rt int) int {  if L <= l && r <= R {    return st.min[rt]  }  mid := (l + r) >> 1  ans := math.MaxInt32  if L <= mid {    ans = int(math.Min(float64(ans), float64(st.minQuery(L, R, l, mid, rt<<1))))  }  if R > mid {    ans = int(math.Min(float64(ans), float64(st.minQuery(L, R, mid+1, r, rt<<1|1))))  }  return ans}
// 为了测试func randomArray(n, v int) []int {  arr := make([]int, n)  for i := 0; i < n; i++ {    arr[i] = rand.Intn(v)  }  return arr}
// 为了测试func main() {  rand.Seed(time.Now().UnixMilli())  fmt.Println("例子测试开始")  arr := []int{3, 1, 4, 3, 1, 2}  fmt.Println(days1(arr))  fmt.Println(days2(arr))  fmt.Println("例子测试结束")
  N := 100  V := 100000  testTimes := 1000  fmt.Println("随机测试开始")  for i := 0; i < testTimes; i++ {    n := rand.Intn(N) + 1    diamonds := randomArray(n, V)    ans1 := days1(diamonds)    ans2 := days2(diamonds)    if ans1 != ans2 {      fmt.Println("出错了!")    }  }  fmt.Println("随机测试结束")
  fmt.Println("性能测试开始")  n := 100000  v := 1000000000  diamonds := randomArray(n, V)  fmt.Println("宝石数量 : ", n)  fmt.Println("价值范围 : ", v)  start := time.Now()  days2(diamonds)  end := time.Now()  fmt.Println("运行时间 : ", end.Sub(start).Milliseconds(), " 毫秒")  fmt.Println("性能测试结束")}

复制代码

rust 完整代码如下：

use std::cmp;use std::time::SystemTime;
struct IndexTree {    tree: Vec<i64>,    n: i64,}
impl IndexTree {    fn new(size: i64) -> IndexTree {        let tree = vec![0; (size + 1) as usize];        let mut it = IndexTree {            tree: tree,            n: size,        };        for i in 1..=size {            it.add(i, 1);        }        it    }
    fn sum(&self, mut i: i64) -> i64 {        let mut ret = 0;        while i > 0 {            ret += self.tree[i as usize];            i -= i & -i;        }        ret    }
    fn sum_range(&self, l: i64, r: i64) -> i64 {        self.sum(r) - self.sum(l - 1)    }
    fn add(&mut self, mut i: i64, d: i64) {        while i <= self.n {            self.tree[i as usize] += d;            i += i & -i;        }    }}
struct SegmentTree {    n: i64,    min: Vec<i64>,}
impl SegmentTree {    fn new(arr: &[i64]) -> SegmentTree {        let n = arr.len() as i64;        let min = vec![0; ((n + 1) << 2) as usize];        let mut st = SegmentTree { n: n, min: min };        for i in 1..=n {            st.update(i, arr[(i - 1) as usize]);        }        st    }
    fn update(&mut self, i: i64, v: i64) {        self.update_segment(i, i, v, 1, self.n, 1);    }
    fn update_segment(&mut self, L: i64, R: i64, C: i64, l: i64, r: i64, rt: i64) {        if L <= l && r <= R {            self.min[rt as usize] = C;            return;        }        let mid = (l + r) >> 1;        if L <= mid {            self.update_segment(L, R, C, l, mid, rt << 1);        }        if R > mid {            self.update_segment(L, R, C, mid + 1, r, rt << 1 | 1);        }        self.push_up(rt);    }
    fn push_up(&mut self, rt: i64) {        self.min[rt as usize] = cmp::min(            self.min[(rt << 1) as usize],            self.min[(rt << 1 | 1) as usize],        );    }
    fn min_query(&self, L: i64, R: i64, l: i64, r: i64, rt: i64) -> i64 {        if L <= l && r <= R {            return self.min[rt as usize];        }        let mid = (l + r) >> 1;        let mut ans = i64::MAX;        if L <= mid {            ans = cmp::min(ans, self.min_query(L, R, l, mid, rt << 1));        }        if R > mid {            ans = cmp::min(ans, self.min_query(L, R, mid + 1, r, rt << 1 | 1));        }        ans    }
    fn min(&self, l: i64, r: i64) -> i64 {        self.min_query(l, r, 1, self.n, 1)    }}
fn days1(diamonds: &mut [i64]) -> i64 {    let mut arr = diamonds.to_vec();    let mut ans = 0;    while !arr.is_empty() {        ans += 1;        deal(&mut arr);    }    ans}
fn deal(arr: &mut Vec<i64>) {    let head = arr.remove(0);    let mut min0 = head;    for a in arr.iter() {        min0 = min0.min(*a);    }    if head > min0 {        arr.push(head);    }}
fn days2(diamonds: &[i64]) -> i64 {    let n = diamonds.len() as i64;    let mut it = IndexTree::new(n);    let mut st = SegmentTree::new(diamonds);    let mut days = 0;    let mut find = 1;    let mut start = 1;    while it.sum_range(1, n) != 0 {        find = find_min(&st, start, n);        days += days_count(&it, start, find, n);        it.add(find, -1);        st.update(find, i64::MAX);        start = find;    }    days}
fn find_min(st: &SegmentTree, start: i64, n: i64) -> i64 {    let (mut l, mut r, mut min) = (n, 1, st.min(1, n));    if st.min(start, n) == min {        l = start;        r = n;    } else {        l = 1;        r = start - 1;    }    let (mut m, mut ans) = (-1, -1);    while l <= r {        m = (l + r) >> 1;        if st.min(l, m) == min {            ans = m;            r = m - 1;        } else {            l = m + 1;        }    }    ans}
fn days_count(it: &IndexTree, start: i64, find: i64, n: i64) -> i64 {    if start <= find {        it.sum_range(start, find)    } else {        it.sum_range(start, n) + it.sum_range(1, find)    }}
fn random_array(n: i64, v: i64) -> Vec<i64> {    let mut arr = vec![0; n as usize];    for i in 0..n {        arr[i as usize] = ((rand::random::<i64>() % v) + v) % v;    }    arr}
fn main() {    let now = SystemTime::now();
    println!("例子测试开始");    let arr = vec![3, 1, 4, 3, 1, 2];    println!("{}", days1(&mut arr.to_vec()));    println!("{}", days2(&arr));    println!("例子测试结束");
    let n = 100;    let v = 100000;    let test_times = 1000;    println!("随机测试开始");    for _ in 0..test_times {        let n = ((rand::random::<i64>() % n) + n) % n + 1;        let diamonds = random_array(n, v);        let ans1 = days1(&mut diamonds.clone());        let ans2 = days2(&diamonds);        if ans1 != ans2 {            println!("出错了!");        }    }    println!("随机测试结束");
    println!("性能测试开始");    let n = 100000;    let v = 1000000000;    let diamonds = random_array(n, v);    println!("宝石数量 : {}", n);    println!("价值范围 :  {}", v);    let start = SystemTime::now();    days2(&diamonds);    let end = SystemTime::now();    println!(        "运行时间 : {} 毫秒",        end.duration_since(start).unwrap().as_millis()    );
    println!("性能测试结束");}

复制代码

发布于: 刚刚阅读数: 4

原文链接:【http://xie.infoq.cn/article/30715258653cd3fc57c4b1fe5】。

福大大架构师每日一题

关注

公众号：福大大架构师每日一题 2021-02-15 加入

公众号：福大大架构师每日一题

发布

暂无评论

创作场景

2023-06-20：给定一个长度为 N 的数组 arr，arr[i] 表示宝石的价值 你在某天遇到 X 价值的宝石， X 价值如果是所有剩余宝石价值中的最小值，你会将该宝石送人 X 价值如果不是所有剩余宝石价值中的

go 完整代码如下：

rust 完整代码如下：

福大大架构师每日一题

评论

2023-06-20：给定一个长度为 N 的数组 arr，arr[i] 表示宝石的价值你在某天遇到 X 价值的宝石， X 价值如果是所有剩余宝石价值中的最小值，你会将该宝石送人 X 价值如果不是所有剩余宝石价值中的