查找数组中重复的数字

        题目来源于《剑指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 条评论
登录 后参与评论

相关文章

来自专栏Esofar 开发日记

JavaScript权威指南 - 数组

JavaScript数组是一种特殊类型的对象。 JavaScript数组元素可以为任意类型,最大容纳232-1个元素。 JavaScript数组是动态的,有...

774
来自专栏技术博客

C#基础知识系列三(类和结构体、String和StringBuilder、equals和==)

   这一节主要来了解一下类和结构体之间的异同点、以及针对String和StringBuilder的用法、equals和==,其实可以看出很多地方都用到了上一节...

864
来自专栏有趣的Python

6-Java基础语法-数组之一维数组

局部变量和数组的默认值问题: 局部变量是没有默认值的,如果没有初始化,是内存中的随机值。而数组是有默认值的0的,因为数组本身是对象。

1233
来自专栏程序员互动联盟

【编程基础】Java初始化有何玄机?

对于Java的初始化顺序大家应该清楚,之前在网站上面有专门的讲解,大家可以通过文章下面的“查看原文”来阅读。 初始化顺序总结起来就是: 1、无继承情况的初始化顺...

3589
来自专栏程序员的知识天地

Python列表最常见的问题【总结】

列表是Python中使用最多的一种数据结果,如何高效操作列表是提高代码运行效率的关键,本文总结了一些python列表最常见的问题,希望能对大家有帮助。

962
来自专栏coding for love

JS原生引用类型解析2-Array类型

(注1:如果有问题欢迎留言探讨,一起学习!转载请注明出处,喜欢可以点个赞哦!) (注2:更多内容请查看我的目录。)

1072
来自专栏积累沉淀

JavaScript对象和数组

学习要点: 1.Object类型 2.Array类型 3.对象中的方法 什么是对象,其实就是一种类型,即引用类型。而对象的值就是引用类型的实例。 一...

2025
来自专栏Java成长之路

多态易错题

①②③比较好理解,一般不会出错。④⑤就有点糊涂了,为什么输出的不是”B and B”呢?!!先来回顾一下多态性。

912
来自专栏blackheart的专栏

[C#1] 6-方法

1.实例构造器[.ctor] 默认情况下,对于引用类型,如果我们没有显示的定义实例构造器,则C#编译器会为我们定义一个无参的公有实例构造器。 一个类的实例构造器...

1995
来自专栏JavaEE

redis学习之redis基本数据类型前言:数据类型详解:

1062

扫码关注云+社区