發表新討論
#30178: O(n)


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 ：
2024-04-13 22:06:23
i164. 比對卡片(進階版) -- TOI練習賽202204新手組 | From: [114.25.105.16] | 發表日期 : 2022-05-05 19:00

int prev[100005] 紀錄各個數字前一次出現的index

從左邊和右邊各掃過取min就是答案了

時間複雜度：O(n)

 
#30181: Re: O(n)


linlincaleb@gmail.com (臨末之頌)

學校 : 新北市立板橋高級中學
編號 : 132772
來源 : [111.248.111.135]
最後登入時間 ：
2023-04-01 22:41:13
i164. 比對卡片(進階版) -- TOI練習賽202204新手組 | From: [111.248.101.95] | 發表日期 : 2022-05-05 20:26

int prev[100005] 紀錄各個數字前一次出現的index

從左邊和右邊各掃過取min就是答案了

時間複雜度：O(n)

是下面的陣列還是上面的阿 看不太懂 怎麼找index阿 不是還要用lower_bound嗎

 
#30183: Re: O(n)


fire5386 (becaidorz)

學校 : 國立清華大學
編號 : 115822
來源 : [140.114.217.8]
最後登入時間 ：
2024-04-13 22:06:23
i164. 比對卡片(進階版) -- TOI練習賽202204新手組 | From: [114.25.105.16] | 發表日期 : 2022-05-05 21:02 
for(int i = 0; i < n; ++i) {
	prev[b[i]] = i;
	if(prev[a[i]] != -1) {
		ans[i] = min(ans[i], abs(i - prev[a[i]]));
	}
}

不需要用到lower_bound找位置 這樣複雜度少一個log(n)

 
#30184: Re: O(n)


linlincaleb@gmail.com (臨末之頌)

學校 : 新北市立板橋高級中學
編號 : 132772
來源 : [111.248.111.135]
最後登入時間 ：
2023-04-01 22:41:13
i164. 比對卡片(進階版) -- TOI練習賽202204新手組 | From: [111.248.101.95] | 發表日期 : 2022-05-05 21:30 
for(int i = 0; i < n; ++i) {
	prev[b[i]] = i;
	if(prev[a[i]] != -1) {
		ans[i] = min(ans[i], abs(i - prev[a[i]]));
	}
}

不需要用到lower_bound找位置 這樣複雜度少一個log(n)

哦 受教了 感謝大大分享

 
ZeroJudge Forum