剑指Offer--找出数组中重复的数字(三种解法)

/** * @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 数组的起始元素 * @param end 数组的结束元素 */
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 哈希法查找重复的数字 * 思路： * 从头到尾按照顺序扫描数组的每个数字，当扫描到一个数字的时候，都可以使用O（1）的时间来判断哈希表里是否已经包含了该数字。 * 若没有包含则加入到哈希表中，若发现哈希表中已经存在该数字则代表找到一个重复的数字 * 时间复杂度分析： * O（1） 只需要遍历一遍哈希数组即可获取最终的结果 * 空间复杂度分析： * O（n） 需要额外分配一个哈希数组 * @param numbers 整数数组 * @param length 数组的长度 * @param duplication (输出) 数组中的一个重复的数字 * @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));
    //先要对分配的内存进行初始化操作
    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;

}



/// 方法三：交换数字法 
/** * @brief 找出数组中重复的数字 * 思路： * 扫描到i下标的数字，然后与data[i]和i进行比较，若相等则找到；否则将data[i]和i进行交换 * 时间复杂度分析： * O（n） 平均每个数字只需要交换两个就可以找到位置，只需要一个循环 * 空间复杂度分析： * O（1） 所有的操作都是在原来的数组的基础上进行的，不需要额外分配空间 * * @param numbers 整数数组 * @param length 数组的长度 * @param duplication (输出) 数组中的一个重复的数字 * @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)
        {
    
            //如果第i个位置上的值和当前定位的值相同则说明找到重复的元素
            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 测试是否有重复的数组 * 案例： * 2, 1, 3, 1, 4 // 重复的数字是数组中最小的数字 * 2, 4, 3, 1, 4 //重复的数字是数组中最大的数字 * 2, 4, 2, 1, 4 // 数组中存在多个重复的数字 * 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);
    // 交换查找
    // 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();
}