sorting/
lib.rs

1//! # Sorting
2
3/// 75m Sort Colors
4struct Sol75;
5
6impl Sol75 {
7    pub fn sort_colors(nums: &mut Vec<i32>) {
8        /// Flag Colors Sorting
9        fn sort_flag_colors(nums: &mut Vec<i32>) {
10            let (mut color0, mut color1, mut color2) = (0, 0, nums.len() - 1);
11            while color1 <= color2 && color2 < usize::MAX {
12                match nums[color1] {
13                    2 => {
14                        nums.swap(color1, color2);
15                        color2 = color2.wrapping_sub(1);
16                    }
17                    1 => {
18                        color1 += 1;
19                    }
20                    0 => {
21                        nums.swap(color0, color1);
22                        color0 += 1;
23                        color1 += 1;
24                    }
25                    _ => {}
26                }
27            }
28
29            println!(":: {nums:?}");
30        }
31        sort_flag_colors(&mut nums.to_vec());
32
33        let mut wtr = nums.len() - 1;
34
35        let mut color2 = 0;
36        while color2 <= wtr && wtr < usize::MAX {
37            match nums[color2] {
38                2 => {
39                    nums[color2] = nums[wtr];
40                    nums[wtr] = 2;
41                    wtr = wtr.wrapping_sub(1);
42                }
43                _ => {
44                    color2 += 1;
45                }
46            }
47        }
48
49        let mut color1 = 0;
50        while color1 <= wtr && wtr < usize::MAX {
51            match nums[color1] {
52                1 => {
53                    nums[color1] = nums[wtr];
54                    nums[wtr] = 1;
55                    wtr = wtr.wrapping_sub(1);
56                }
57                _ => {
58                    color1 += 1;
59                }
60            }
61        }
62
63        println!(":: {nums:?}");
64    }
65}
66
67/// 220h Contains Duplicate III
68struct Sol220;
69
70impl Sol220 {
71    pub fn contains_nearby_almost_duplicate(
72        nums: Vec<i32>,
73        index_diff: i32,
74        value_diff: i32,
75    ) -> bool {
76        use std::collections::BTreeSet;
77
78        println!("== {:?}", (&nums, index_diff, value_diff));
79
80        let mut oset = BTreeSet::new();
81        for (i, &n) in nums.iter().enumerate() {
82            println!("-> {:?}", (n, &oset));
83
84            if i > index_diff as usize {
85                let drop = nums[i - index_diff as usize - 1];
86                if n == drop {
87                    continue;
88                }
89
90                oset.remove(&drop);
91            }
92
93            if oset.range(n - value_diff..=value_diff + n).count() > 0 {
94                return true;
95            }
96
97            oset.insert(n);
98        }
99
100        false
101    }
102}
103
104/// 905 Sort Array By Parity
105struct Sol905;
106
107impl Sol905 {
108    pub fn sort_array_by_parity(nums: Vec<i32>) -> Vec<i32> {
109        use std::collections::VecDeque;
110
111        let mut rst = VecDeque::new();
112        nums.into_iter().for_each(|n| match n & 1 {
113            1 => rst.push_back(n),
114            _ => rst.push_front(n),
115        });
116
117        rst.into()
118    }
119}
120
121/// 1356 Sort Integers by The Number of 1 Bits
122struct Sol1356 {}
123
124impl Sol1356 {
125    pub fn sort_by_bits(mut arr: Vec<i32>) -> Vec<i32> {
126        let mut arr_copy = arr.clone();
127        arr_copy.sort_by_key(|&n| (n.count_ones(), n));
128        println!(":? {arr_copy:?}");
129
130        arr.sort_by_key(|&n| {
131            let mut bits = 0;
132            let mut x = n;
133            while x > 0 {
134                bits += x & 1;
135                x >>= 1;
136            }
137            (bits, n)
138        });
139
140        arr
141    }
142}
143
144/// 2410m Maximum Matching of Players With Trainers
145struct Sol2410 {}
146
147impl Sol2410 {
148    pub fn match_players_and_trainers(mut players: Vec<i32>, mut trainers: Vec<i32>) -> i32 {
149        players.sort_unstable();
150        trainers.sort();
151
152        let mut matches = 0;
153        let (mut p, mut t) = (0, 0);
154        while p < players.len() && t < trainers.len() {
155            if players[p] <= trainers[t] {
156                matches += 1;
157                p += 1;
158            }
159            t += 1;
160        }
161
162        matches
163    }
164}
165
166/// 2551h Put Marbles in Bags
167struct Sol2551;
168
169impl Sol2551 {
170    pub fn put_marbles(weights: Vec<i32>, k: i32) -> i64 {
171        let mut pairs: Vec<i64> = weights.windows(2).map(|w| (w[0] + w[1]) as i64).collect();
172        pairs.sort_unstable();
173
174        pairs.iter().skip(weights.len() - k as usize).sum::<i64>()
175            - pairs.iter().take(k as usize - 1).sum::<i64>()
176    }
177}
178
179/// 2948m Make Lexicographically Smallest Array by Swapping Elements
180struct Sol2948;
181
182impl Sol2948 {
183    pub fn lexicographically_smallest_array(nums: Vec<i32>, limit: i32) -> Vec<i32> {
184        let mut nums: Vec<_> = nums.into_iter().enumerate().collect();
185        nums.sort_by_key(|t| t.1);
186        nums.push((nums.len() + 1, i32::MAX));
187
188        println!(" -> {nums:?}");
189
190        let mut rst = vec![0; nums.len()];
191        let mut groups = vec![nums[0].0];
192        let mut p = 0;
193
194        (1..nums.len()).for_each(|i| {
195            if nums[i].1 > nums[i - 1].1 + limit {
196                groups.sort();
197                groups.reverse();
198
199                while let Some(g) = groups.pop() {
200                    rst[g] = nums[p].1;
201                    p += 1;
202                }
203
204                println!(" -> {rst:?}");
205            }
206
207            groups.push(nums[i].0);
208        });
209
210        rst.pop();
211        rst
212    }
213}
214
215#[cfg(test)]
216mod tests;
sorting/lib.rs

sorting/
lib.rs
