Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save dhicksNTIA/8bcfae393a6d77b1f7b08300f5b024dd to your computer and use it in GitHub Desktop.
Save dhicksNTIA/8bcfae393a6d77b1f7b08300f5b024dd to your computer and use it in GitHub Desktop.
/// Find first duplicate integer in vector.
///
/// Assumed that array a contains only number in range [1, a.len()].
/// O(n) time complexity and O(1) memory. NOT PURE FUNCTIONAL.
///
/// # Example
///
/// ```
/// assert!(first_duplicate(vec![8, 4, 6, 2, 6, 4, 7, 9, 5, 8]) == 6);
/// assert!(first_duplicate(vec![2, 1, 4, 5, 3]) == -1);
/// ```
fn first_duplicate(mut a: Vec<i32>) -> i32 {
for index in 0..a.len() {
let number = a[index].abs() as usize;
let relative_index = number - 1;
if let Some(elem) = a.get_mut(relative_index) {
*elem *= -1;
if elem.is_positive() {
return number as i32;
}
}
}
-1
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment