查找数组中重复的数字

        题目来源于《剑指Offer》中的面试题3:找出数组中重复的数字。   // 题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,   // 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如,如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3},   // 那么对应的输出是重复的数字2或者3。

        解决方法有多种,包括数组排序,哈希表法,以及作者推荐的重排数组法。此处介绍自己的一个做法,以空间换时间,通过新建数组来实现快速查找,具体做法是新建长度为length的数组newArray,初始化值为-1;将numbers数组的值依次作为newArray的下标和对应的值为newArray赋值,其中number向newArray赋值时,判断newArray对应下标是否为-1,如果不为-1则表示newArray曾被相同的数赋值,说明有重复的数存在。以数组{2,3,1,0,2,5,3}为例,新建长度为7的数组{-1,-1,-1,-1,-1,-1,-1},依次赋值为{-1,-1,2,-1,-1,-1,-1},{-1,-1,2,3,-1,-1,-1},{-1,1,2,3,-1,-1,-1},{0,1,2,3,-1,-1,-1},下一次将2赋值给新数组时,发现新数组中下标为2的为2,说明曾被2赋值,说明2是重复的。

#include<cstdio>

// 参数:
//        numbers:     一个整数数组
//        length:      数组的长度
//        duplication: (输出) 数组中的一个重复的数字
// 返回值:             
//        true  - 输入有效,并且数组中存在重复的数字
//        false - 输入无效,或者数组中没有重复的数字
//bool duplicate(int numbers[], int length, int* duplication)
//{
//    // int* duplication 使用指针类型的形参访问函数外部的对象,通过指针可以访问和修改指向的对象,但是拷贝的指针是两个不同的指针
//    // 建议使用引用类型的形参替代指针
//    if (numbers == nullptr || length <= 0)
//        return false;
//
//    for (int i = 0; i < length; ++i)
//    {
//        if (numbers[i] < 0 || numbers[i] > length - 1)
//            return false;
//    }
//
//    for (int i = 0; i < length; ++i)
//    {
//        while (numbers[i] != i)
//        {
//            if (numbers[i] == numbers[numbers[i]])
//            {
//                *duplication = numbers[i];  //解引用
//                return true;
//            }
//
//            // 交换numbers[i]和numbers[numbers[i]]             
//            int temp = numbers[i];
//            numbers[i] = numbers[temp];
//            numbers[temp] = temp;
//        }
//    }
//    return false;
//}

/*
    我的新方法:
    新建长度为length的数组newArray,初始化值为-1;
    将numbers数组的值作为newArray的下标和对应的值为newArray赋值,
    其中number向newArray赋值时,判断newArray对应下标是否为-1,
    如果不为-1则表示newArray曾被相同的数赋值,说明有重复的数存在
*/
bool duplicate(int numbers[], int length, int* duplication)
{
    // 过滤掉空指针和不符合规定的输入
    if (numbers == nullptr || length <= 0)
        return false;

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

    int* tempArray = new int[length]; //动态数组
    for (int * q= tempArray;q!= tempArray+length;++q)
    {
        // 遍历数组初始化
        *q = -1;
    }
    for (int j = 0; j < length; j++)
    {
        if (tempArray[numbers[j]] == -1)
            tempArray[numbers[j]] = numbers[j];
        else if(tempArray[numbers[j]]== numbers[j])
        {
            //曾被赋值一次或多次
            *duplication = numbers[j];  //解引用
            delete [] tempArray;
            return true;
        }
    }
    delete [] tempArray; //删除指向数组的指针,不可省略方括号
    return false;
}

// ====================测试代码====================
bool contains(int array[], int length, int number)
{
    for (int i = 0; i < length; ++i)
    {
        //只要有一个符合,即返回True
        if (array[i] == number)
            return true;
    }
    return false;
}

void test(char* testName, int numbers[], int lengthNumbers, int expected[], int expectedExpected, bool validArgument)
{
    printf("%s begins: ", testName);
    // expected[];  重复结果
    // expectedExpected; 重复数量 
    int duplication;  //自定义函数重复数
    bool validInput = duplicate(numbers, lengthNumbers, &duplication);

    if (validArgument == validInput)
    {
        //是否有重复
        if (validArgument)
        {
            if (contains(expected, expectedExpected, duplication))
                printf("Passed.\n");
            else
                printf("FAILED.\n");
        }
        else
            printf("Passed.\n");
    }
    else
        printf("FAILED.\n");
}

// 重复的数字是数组中最小的数字
void test1()
{
    int numbers[] = { 2, 1, 3, 1, 4 };
    int duplications[] = { 1 };
    test("Test1", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true);
}

// 重复的数字是数组中最大的数字
void test2()
{
    int numbers[] = { 2, 4, 3, 1, 4 };
    int duplications[] = { 4 };
    test("Test2", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true);
}

// 数组中存在多个重复的数字
void test3()
{
    int numbers[] = { 2, 4, 2, 1, 4 };
    int duplications[] = { 2, 4 };
    test("Test3", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), true);
}

// 没有重复的数字
void test4()
{
    int numbers[] = { 2, 1, 3, 0, 4 };
    int duplications[] = { -1 }; // not in use in the test function
    test("Test4", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), false);
}

// 没有重复的数字
void test5()
{
    int numbers[] = { 2, 1, 3, 5, 4 };
    int duplications[] = { -1 }; // not in use in the test function
    test("Test5", numbers, sizeof(numbers) / sizeof(int), duplications, sizeof(duplications) / sizeof(int), false);
}

// 无效的输入
void test6()
{
    int* numbers = nullptr;
    int duplications[] = { -1 }; // not in use in the test function
    test("Test6", numbers, 0, duplications, sizeof(duplications) / sizeof(int), false);
}

void main()
{
    test1();
    test2();
    test3();
    test4();
    test5();
    test6();
    getchar();
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术碎碎念

python3 入门 (四) 类与继承

Python 类 Python中的类提供了面向对象编程的所有基本功能:类的继承机制允许多个基类,派生类可以覆盖基类中的任何方法,方法中可以调用基类中的同名方法。...

35212
来自专栏python3

python3--中一些常见的坑(机制上的问题)

重点:在循环一个列表时,最好不要进行删除的动作(一旦删除,索引会随之改变),容易错误。

541
来自专栏Java Edge

深入理解Java-final关键字1 修饰属性或者变量2 修饰方法3 修饰类4 final关键字的好处5 不可变类6其他重要知识点

2676
来自专栏星汉技术

Scala中的集合类型

38210
来自专栏深度学习之tensorflow实战篇

python yield函数深入浅出理解

首先关于生成器的那些事: 1.通常的for…in…循环中,in后面是一个数组,这个数组就是一个可迭代对象,类似的还有链表,字符串,文件。它的缺陷是所有数据都...

2964
来自专栏前端桃园

JavaScript核心概念(1):类型转换

看到这个是不是有一种想打人的感觉,垃圾 JavaScript,这特么都什么鬼,相信很多人不管是笔试还是面试,都被 JS 的类型转换难道过,相信认真看完我这篇文章...

614
来自专栏从流域到海域

Python yield关键字 和 Generator(生成器)

Generators functions allow you to declare a function that behaves like an itera...

21210
来自专栏C/C++基础

字符数组的初始化与赋值

C语言中表示字符串有两种方式,数组和指针,字符数组是我们经常使用的方式。变量的定义包括指明变量所属类型、变量名称、分配空间以及初始化。可以看出,变量的初始化是变...

592
来自专栏GreenLeaves

Js正则Replace方法

JS正则的创建有两种方式: new RegExp() 和 直接字面量。 //使用RegExp对象创建 var regObj = new RegExp("(^\s...

22010
来自专栏我是业余自学C/C++的

virtual

1305

扫码关注云+社区