2022-07-17:1, 2, 3... N-1, N, n+1, n+2... In this sequence, only one number has repetition (n). This sequence is unordered. Find the repeated number n. This sequence is ordered. Find the repeated numb

2022-07-17：1、2、3…n-1、n、n、n+1、n+2…
In this sequence , Only one number repeats (n).
This sequence is disordered , Find duplicate numbers n.
This sequence is ordered , Find duplicate numbers n.

answer 2022-07-17：

Cannot use hash table .
First question , The two methods , Fast and slow pointer ring finding problem and XOR method .
Second questions , Dichotomy .

The code to use rust To write . The code is as follows ：

use rand::Rng;
use std::collections::HashSet;
fn main() {
    
    let nn: i32 = 10;
    let test_time: i32 = 3000;
    println!(" Beginning of the test ");
    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!(" Error in unsorted condition ! Fast and slow pointer mode ");
            break;
        }
        if right(&mut arr2) != find_duplicate2(&mut arr2) {
    
            println!(" Error in unsorted condition ! Exclusive or mode ");
            break;
        }
        arr.sort();
        if right(&mut arr) != find_duplicate_sorted(&mut arr) {
    
            println!(" Error in sorting ! Dichotomy ");
            break;
        }
    }
    println!(" End of test ");
}

//  In order to test 
//  Absolutely right , But traverse directly + Hashtable , There is no way to score 
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;
}

//  Meet the requirements of the topic 、 Unordered array , Find duplicates 
//  Time complexity O(N), Extra space complexity O(1)
//  Use the speed pointer 
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];
    }
    //  Meet again ！ One conclusion 
    return slow;
}

//  Meet the requirements of the topic 、 Unordered array , Find duplicates 
//  Time complexity O(N), Extra space complexity O(1)
//  Using XOR 
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];
    }

    //  Meet again ！ One conclusion 
    return ans;
}

//  Meet the requirements of the topic 、 Ordered array , Find duplicates 
//  Time complexity O(logN), Extra space complexity 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;
}

//  In order to test 
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;
}

The results are as follows ：

---

Zuo Shen java Code