2022-07-17：1、2、3...n-1、n、n、n+1、n+2... 在这个序列中，只有一个数字有重复(n)。 这个序列是无序的，找到重复数字n。 这个序

use rand::Rng;
use std::collections::HashSet;
fn main() {
    let nn: i32 = 10;
    let test_time: i32 = 3000;
    println!("测试开始");
    for _ in 0..test_time {
        let mut arr = random_array(rand::thread_rng().gen_range(0, nn) + 1);
        let mut arr2 = arr.clone();
        if right(&mut arr) != find_duplicate(&mut arr) {
            println!("未排序情况出错!快慢指针方式");
            break;
        }
        if right(&mut arr2) != find_duplicate2(&mut arr2) {
            println!("未排序情况出错!异或方式");
            break;
        }
        arr.sort();
        if right(&mut arr) != find_duplicate_sorted(&mut arr) {
            println!("排序情况出错!二分法");
            break;
        }
    }
    println!("测试结束");
}

// 为了测试
// 绝对正确，但是直接遍历+哈希表，没有得分的方法
fn right(arr: &mut Vec<i32>) -> i32 {
    let mut set: HashSet<i32> = HashSet::new();
    for num in arr.iter() {
        if set.contains(num) {
            return *num;
        }
        set.insert(*num);
    }
    return -1;
}

// 符合题目要求的、无序数组，找重复数
// 时间复杂度O(N)，额外空间复杂度O(1)
// 用快慢指针
fn find_duplicate(arr: &mut Vec<i32>) -> i32 {
    if arr.len() < 2 {
        return -1;
    }
    let mut slow = arr[0];
    let mut fast = arr[arr[0] as usize];
    while slow != fast {
        slow = arr[slow as usize];
        fast = arr[arr[fast as usize] as usize];
    }
    // slow == fast
    fast = 0;
    while slow != fast {
        fast = arr[fast as usize];
        slow = arr[slow as usize];
    }
    // 再相遇！一个结论
    return slow;
}

// 符合题目要求的、无序数组，找重复数
// 时间复杂度O(N)，额外空间复杂度O(1)
// 用异或
fn find_duplicate2(arr: &mut Vec<i32>) -> i32 {
    if arr.len() < 2 {
        return -1;
    }

    let mut ans = 0;

    for i in 0..arr.len() as i32 {
        ans ^= i;
    }

    for i in 0..arr.len() as i32 {
        ans ^= arr[i as usize];
    }

    // 再相遇！一个结论
    return ans;
}

// 符合题目要求的、有序数组，找重复数
// 时间复杂度O(logN)，额外空间复杂度O(1)
fn find_duplicate_sorted(arr: &mut Vec<i32>) -> i32 {
    if arr.len() < 2 {
        return -1;
    }
    let mut l: i32 = 0;
    let mut r: i32 = arr.len() as i32 - 1;
    let mut m: i32;
    let mut ans = -1;
    while l <= r {
        m = (l + r) / 2;
        if (m - 1 >= 0 && arr[(m - 1) as usize] == arr[m as usize])
            || (m + 1 < arr.len() as i32 && arr[(m + 1) as usize] == arr[m as usize])
        {
            ans = arr[m as usize];
            break;
        }
        if m - l == arr[m as usize] - arr[l as usize] {
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    return ans;
}

// 为了测试
fn random_array(n: i32) -> Vec<i32> {
    let mut ans: Vec<i32> = vec![];
    for i in 0..n + 1 {
        ans.push(i + 1);
    }
    ans[n as usize] = rand::thread_rng().gen_range(0, n) + 1;
    let mut i = n;
    while i > 0 {
        let j = rand::thread_rng().gen_range(0, i + 1);
        let tmp = ans[i as usize];
        ans[i as usize] = ans[j as usize];
        ans[j as usize] = tmp;

        i -= 1;
    }
    return ans;
}