The sword refers to Offer--find the repeated numbers in the array (three solutions)

/** * @file 03_01_code.cpp * @author panzhongsheng ([email protected]) * @brief 找出数组中重复的数字 * 题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内.数组中某些数字是重复的,但不知道有几个数字重复了, * 也不知道每个数字重复了几次.请找出数组中任意一个重复的数字.例如,如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}, * 那么对应的输出是重复的数字2或者3. * @version 0.1 * @date 2022-08-01 * * @copyright Copyright (c) 2022 * */
#include <iostream>
using namespace std;


/** * @brief 交换两个数 * @param first_num 第一个数 * @param second_num 第二个数 */
void swap(int *first_num, int *second_num)
{
    
    int tmp;
    tmp = *first_num;
    *first_num = *second_num;
    *second_num = tmp;
}

bool checkNumbers(int numbers[], int length)
{
    
    if(numbers == nullptr || length < 0)
    {
    
        return false;
    }
    for(int i = 0; i < length; i++)
    {
    
        if(numbers[i] < 0 || numbers[i] > length - 1)
        {
    
            return false;
        }
    }
    return true;
}

void printfNumbers(int numbers[], int length)
{
    
    printf("Numbers:");
    for(int i = 0; i < length; i++)
    {
    
        printf("%d ", numbers[i]);
    }
    printf("\n");
}

/// 方法二：排序法 
/** * @brief 快速排序 * 思路： * 每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边. * @param numbers 待排序的数组 * @param begin The starting element of the array * @param end The ending element of the array */
void quickSort(int numbers[], int left, int right)
{
    
   	int i, j, t, temp;
	if(left > right)
		return;
    temp = numbers[left]; //temp中存的就是基准数
    i = left;
    j = right;
    while(i != j) {
     //顺序很重要,要先从右边开始找
    	while(numbers[j] >= temp && i < j)
    		j--;
    	while(numbers[i] <= temp && i < j)//再找右边的
    		i++;       
    	if(i < j)//交换两个数在数组中的位置
    	{
    
    		t = numbers[i];
    		numbers[i] = numbers[j];
    		numbers[j] = t;
    	}
    }
    //最终将基准数归位
    numbers[left] = numbers[i];
    numbers[i] = temp;
    quickSort(numbers, left, i-1);//继续处理左边的,这里是一个递归的过程
    quickSort(numbers, i+1, right);//继续处理右边的 ,这里是一个递归的过程

}


bool quickSortfindDuplicateNumber(int numbers[], int length, int *duplication)
{
    
    if(checkNumbers(numbers, length) == false)
    {
    
        printf("checkNumbers failed\n");
        return false;
    }
    quickSort(numbers, 0, length - 1);
    for(int i = 0; i < length - 1; i++)
    {
    
        if(numbers[i] == numbers[i+1])
        {
    
            *duplication = numbers[i];
            printf("Duplicate number:%d\n", *duplication);
            return true;
        }
    }
    return false;
}

/// 方法二：哈希法 

/** * @brief Hash finds duplicate numbers * 思路： * Scan each number of the array in order from the beginning to the end,When scanning a number,都可以使用O（1）的时间来判断哈希表里是否已经包含了该数字. * If not included, it will be added to the hash table,If it is found that the number already exists in the hash table, it means that a duplicate number is found * 时间复杂度分析： * O（1） Just traverse the hash array once to get the final result * 空间复杂度分析： * O（n） An additional hash array needs to be allocated * @param numbers 整数数组 * @param length 数组的长度 * @param duplication (输出) A repeating number in an array * @return true 输入有效,并且数组中存在重复的数字 * @return false 输入无效,或者数组中没有重复的数字 */
bool findDuplicateNumberByHash(int numbers[], int length, int *duplication)
{
    
    if(checkNumbers(numbers, length) == false)
    {
    
        printf("checkNumbers failed\n");
        return false;
    }
    //malloc以字节为单位
    int* hash_numbers = (int*)malloc(sizeof(sizeof(int)*length));
    //The allocated memory must be initialized first
    for(int i = 0; i < length; i++)
    {
    
        hash_numbers[i] = 0;

    }
    for(int i = 0; i < length; i++)
    {
    
        hash_numbers[numbers[i]] += 1;
        if(hash_numbers[numbers[i]] >= 2)
        {
    
            *duplication = numbers[i];
            return true;
        }
    }
    return false;

}



/// 方法三：Swap numbers 
/** * @brief 找出数组中重复的数字 * 思路： * 扫描到i下标的数字,然后与data[i]和i进行比较,If they are equal, they are found;否则将data[i]和i进行交换 * 时间复杂度分析： * O（n） On average each number only needs to be swapped two to find the location,只需要一个循环 * 空间复杂度分析： * O（1） All operations are performed on the basis of the original array,不需要额外分配空间 * * @param numbers 整数数组 * @param length 数组的长度 * @param duplication (输出) A repeating number in an array * @return true 输入有效,并且数组中存在重复的数字 * @return false 输入无效,或者数组中没有重复的数字 * */
bool findDuplicateNumber(int numbers[], int length, int *duplication)
{
    
    
    if(checkNumbers(numbers, length) == false)
    {
    
        return false;
    }
    for(int i = 0; i < length; i++)
    {
    
        while(numbers[i] != i)
        {
    
            //如果第iThe value at the position is the same as the value of the current position, indicating that a duplicate element was found
            if(numbers[i] == numbers[numbers[i]])
            {
    
                *duplication = numbers[i];
                return true;
            }
            //否则交换numbers[i]和numbers[numbers[i]]
            swap(&numbers[i],&numbers[numbers[i]]);
        }
    }
    return false;

}

/** * @brief Test for duplicate arrays * 案例： * 2, 1, 3, 1, 4 // Repeated numbers are the smallest numbers in the array * 2, 4, 3, 1, 4 //重复的数字是数组中最大的数字 * 2, 4, 2, 1, 4 // There are multiple duplicate numbers in the array * 2, 1, 3, 0, 4 // 没有重复的数字 * -1 // 无效的输入 */
void test()
{
    
    bool find_flag = false;
    int numbers[] = {
       2, 1, 3, 1, 4  };
    int duplications;
    // 排序查找
    // find_flag = quickSortfindDuplicateNumber(numbers, sizeof(numbers) / sizeof(numbers[0]), &duplications);
    // exchange lookup
    // find_flag = findDuplicateNumber(numbers, sizeof(numbers) / sizeof(numbers[0]), &duplications);
    //哈希查找
    find_flag = findDuplicateNumberByHash(numbers, sizeof(numbers) / sizeof(numbers[0]), &duplications);
    if(find_flag == true)
    {
    
        printf("found duplicate number %d\n", duplications);
    }
    else
    {
    
        printf("Not found duplicate number or Input Invalid\n");
    }
}



int main(int argc, char **argv)
{
    
    test();
}