资讯专栏INFORMATION COLUMN

剑指offer之基础知识数组

zhou_you / 1909人阅读

摘要:附上和实现二维数组中的查找题目描述在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

为了实习的准备,开始刷题来巩固基础算法和数据结构,大神轻喷。

1.数组中重复的数字

题目描述:在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

思路分析:主要看题数字正好是在0到n-1的范围。在不重复的情况下,数组的每个下标对应一个数字。对于数组{2,3,1,0,2,5,3},第0个元素是2,与第二个元素1交换{1,3,2,0,2,5,3},再与第一个元素3交换{3,1,2,0,2,5,3},再与第三个元素0交换{0,1,2,3,2,5,3},将数组第0个元素变为0,依次交换查找,当有一个元素重复出现2次,返回即可。

附上c++和js实现

bool duplicate(int numbers[], int length, int* duplication) {
    if(numbers==nullptr||length<=0){
        return false;
    }
    for(int i=0;ilength-1){
            return false;
        }
    }
    for(int i=0;i
function duplicate(numbers, duplication)
{
    if(numbers.length<=0){
        return false;
    }
    for(let i=0;inumbers.length-1){
            return false;
        }
    }
    for(let i=0;i

2.二维数组中的查找

题目描述:在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

思路分析:矩阵分析,从矩阵的右上角或者左下角开始查找元素。我是从右上角开始查找,当右上角元素本身就是要查找的元素,直接返回,若查找的元素比它小,则左移并减少列数,反之同理,若查找的元素比它大,则右移并增大行数,直到找到返回或没找到。

bool Find(int target, vector > array) {
    bool found=false;
    int rowCount=array.size();
    int colCount=array[0].size();
    if(rowCount>0&&colCount>0){
        int row=0;
        int col=colCount-1;
        while(row=0){
            if(target==array[row][col]){
                found=true;
                break;
            }
            if(targetarray[row][col]){
                row++;
            }
        }
    }
    return found;
}
function Find(target, array)
{
    // write code here
    let rowCount=array.length;
    let colCount=array[0].length;
    if(rowCount>0&&colCount>0){
        let row=0;
        let col=colCount-1;
        while(row=0){
            if(target==array[row][col]){
                return true;
                break;
            }
            if(targetarray[row][col]){
                row++;
            }
        }
    }
    return false;
}

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/92489.html

相关文章

  • JavaSE与数据结构基础知识系列——专栏导航

    ⭐️前面的话⭐️ 大家好!这是Java基础知识与数据结构博文的导航帖,收藏我!学习Java不迷路! ?博客主页:未见花闻的博客主页 ?欢迎关注?点赞?收藏⭐️留言? ?本文由未见花闻原创,CSDN首发! ?首发时间:?2021年11月11日? ✉️坚持和努力一定能换来诗与远方! ?参考书籍:?《Java核心技术卷1》,?《Java核心技术卷2》,?《Java编程思想》 ?参考在线编程网站:?牛...

    Cc_2011 评论0 收藏0
  • 剑指offer系列——剑指 Offer 06. 从尾到头打印链表(C语言)

    摘要:导航小助手剑指从尾到头打印链表题目详情解题思路源代码总结剑指从尾到头打印链表题目详情输入一个链表的头节点,从尾到头反过来返回每个节点的值用数组返回。时间复杂度方法先反转链表并求长度,在将反转后的链表数据拷贝至数组中。 ...

    DevTTL 评论0 收藏0
  • PHPer也刷《剑指Offer链表

    摘要:剑指中链表相关题目俗话说光说不练假把式,既然学习了链表的基础概念和基本操作那我们一定要找些题目巩固下,下面来看剑指中的相关题目。题目分析合并两个排序的链表,需要分别比较两个链表的每个值,然后改变指针。 温故知新 链表由一个一个的作为节点的对象构成的,每一个节点都有指向下一个节点的指针,最后一个节点的指针域指向空。每个节点可以存储任何数据类型。 根据类型可以分为单链表、双链表、环形链表、...

    daydream 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<