#30178: O(n)


fire5386 (Penguin07)

School : 國立清華大學
ID : 115822
IP address : [114.25.65.150]
Last Login :
2022-07-03 21:33:33
i164. 比對卡片(進階版) -- TOI練習賽202204新手組 | From: [114.25.105.16] | Post Date : 2022-05-05 19:00

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

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

時間複雜度:O(n)

 
#30181: Re: O(n)


linlincaleb@gmail.com (臨末之頌)

School : 新北市立板橋高級中學
ID : 132772
IP address : [111.248.185.37]
Last Login :
2022-06-18 16:32:20
i164. 比對卡片(進階版) -- TOI練習賽202204新手組 | From: [111.248.101.95] | Post Date : 2022-05-05 20:26

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

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

時間複雜度:O(n)

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

 
#30183: Re: O(n)


fire5386 (Penguin07)

School : 國立清華大學
ID : 115822
IP address : [114.25.65.150]
Last Login :
2022-07-03 21:33:33
i164. 比對卡片(進階版) -- TOI練習賽202204新手組 | From: [114.25.105.16] | Post Date : 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 (臨末之頌)

School : 新北市立板橋高級中學
ID : 132772
IP address : [111.248.185.37]
Last Login :
2022-06-18 16:32:20
i164. 比對卡片(進階版) -- TOI練習賽202204新手組 | From: [111.248.101.95] | Post Date : 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