プログラミングのお題スレ Part22 (857ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
781: デフォルトの名無しさん [sage] 2025/07/27(日) 21:43:59.43 ID:w39E9j9Q(1) AAS
>>771771(22): デフォルトの名無しさん [sage] 2025/07/25(金) 12:30:11.02 ID:CjDQVF2B(1) AAS
【問題】
整数のリストが与えられたとき、そのリストを昇順に安定ソートした時の各要素のインデクス（0開始）を対応させたリストを作成せよ
【例】
入力： 1 100 10 10000 1000
出力： 0 2 1 4 3
入力： 3 1 4 1 5 9 2
出力： 3 0 4 1 5 6 2
入力： 0 1 0 1 0 1 0 1
出力： 0 4 1 5 2 6 3 7
実際に必要になって実装したけどスマートな方法があったら知りたい
Rust
既に色々と出ているため別の観点からのコード
一時作業メモリ最小 ＆ ソートは1回 ＆ ジェネリック
fn f<T: std::cmp::Ord>(input: &[T]) -> Vec<usize> {
let len = input.len();
// ポジションのリスト [0, 1, 2, 3, ... , len-1] を作成
let mut pos_list: Vec<usize> = (0..len).collect();
// inputを利用してそのポジションだけをソート
pos_list.sort_by_key(|&pos| &input[pos]);
// 返すべきランクのリスト
let mut rank_list: Vec<usize> = vec![0; len];
// ポジション⇔ランクは逆写像なのでソートは不要
(0..len).for_each(|rank| rank_list[pos_list[rank]] = rank);
rank_list
}
fn main() {
assert_eq!(f(&[1, 100, 10, 10000, 1000]), [0, 2, 1, 4, 3]);
assert_eq!(f(&[3, 1, 4, 1, 5, 9, 2]), [3, 0, 4, 1, 5, 6, 2]);
assert_eq!(f(&[0, 1, 0, 1, 0, 1, 0, 1]), [0, 4, 1, 5, 2, 6, 3, 7]);
}
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.030s