2023-06-20：給定一個長度為N的數(shù)組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的寶石，寶石已經(jīng)沒有了。

所以返回10。

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

1 <= 寶石價值 <= 10的9次方。

來自TikTok美國筆試。

答案2023-06-20：

1.第一個方法(days1)使用了暴力的方式，通過遍歷數(shù)組并移動寶石來模擬每一天的操作，直到所有寶石都被送出。時間復雜度較高。

2.第二個方法(days2)使用了更高效的算法。首先構建了一個支持查詢累加和和最小值的數(shù)據(jù)結構（IndexTree和SegmentTree）。然后利用這些數(shù)據(jù)結構來計算送出所有寶石需要的天數(shù)。具體步驟如下：

2.1.初始化累加和數(shù)據(jù)結構(it)和最小值數(shù)據(jù)結構(st)。

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

2.3.計算從起始位置到最小值之間的寶石總數(shù)(daysCount)。

2.4.將最小值送出，更新累加和數(shù)據(jù)結構(it)和最小值數(shù)據(jù)結構(st)。

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

2.6.重復上述步驟直到所有寶石都被送出。

2.7.返回送出寶石所需的天數(shù)。

時間復雜度和空間復雜度如下：

方法1（days1）：

• ??時間復雜度：$O(N^2)$，其中N是寶石數(shù)組的長度。需要遍歷數(shù)組N次，并且在每次操作中需要移動寶石，移動的次數(shù)也達到了N次。

• ??空間復雜度：O(N)，需要額外的存儲空間來存儲寶石數(shù)組。

方法2（days2）：

• ??時間復雜度：$O(N * (logN)^2)$，其中N是寶石數(shù)組的長度。構建IndexTree和SegmentTree所需的時間復雜度為O(N * logN)。每次查詢最小值的時間復雜度為O(logN)，總共進行N次查詢。因此，總的時間復雜度為$O(N * (logN)^2)$。

• ??空間復雜度：O(N)，需要額外的存儲空間來構建IndexTree和SegmentTree。

綜上所述，方法1的時間復雜度為$O(N^2)$，方法2的時間復雜度為$O(N * (logN)^2)$。在時間復雜度上，方法2優(yōu)于方法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(后續(xù)....最小值，最左的位置)
????????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("寶石數(shù)量?:?",?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!("寶石數(shù)量?:?{}",?n);
????println!("價值范圍?:??{}",?v);
????let?start?=?SystemTime::now();
????days2(&diamonds);
????let?end?=?SystemTime::now();
????println!(
????????"運行時間?:?{}?毫秒",
????????end.duration_since(start).unwrap().as_millis()
????);

????println!("性能測試結束");
}