随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

09考研数据结构试题的一种解法(Java版)

本文为原创,如需转载,请注明作者和出处,谢谢!   

    虽然研究生已毕业,但看到有一些难度的研究生考试题还是忍不住要做做,本文给出了09年研究生入学考试的一道数据结构题的Java实现。该题的描述如下图所示。


    该题的两种实现一位朋友已经完成了,详见递归和非递归实现 。在本文将给出另外一种算法,该算法的空间复杂度为O(1),时间复杂度为O(n)。这在空间复杂度和时间复杂度上应该是比较优化了。
    本算法的基本思想如下:
    既然是查找倒数第K个结点(注意,不是正数,否则就没什么可讨论的了),而且链表是单向的,还不能改变表结构,这就意味着只能从前往后扫描结点。我们首先要知道这个链表有多少个结点(如果总结点数都不知道,何谈倒数?),这个非常简单,只要从头扫描一下链表,再计一下数即可。
    在同一时间从事多项工作会大大提升效率,当然,扫描链表也不例外,在扫描链表的同时,还需要做一些其他的工作。既然只能从前向后扫描链表,而且要求倒数第K个结点,那就让我们把这个链表按长度为K分成若干块,而最后扫描的结果要么结点数是K的整数倍(模为0),要么余数(模)不为0(多出几个结点,多出的结点数小于K)。
    先看看第二种情况。
    假设有12个结点的链表,每一个结点的值从前往后分别是1至12,如下所示:

    1  2  3  4  5  6  7  8  9  10  11 12

    假设我们要求倒数第5个结点,我们直接就可以看出结果是8。那么用程序如何处理呢?
   
    先按长度为5将上面的结点分成三个区域,如下:

    1 2 3 4 5           6 7 8 9 10           11 12

    注意,不是物理分,而是使用变量来保存区域的边界(也就是区域最后一个结点的对象)。
    从上面的分隔可以看出,最后剩下两个结点,既然是求倒数第5个,而最后剩下了两个,那么还缺5-2=3个,因此,只需要从倒数第二个块(6 7 8 9 10)略过前两个,第三个结点(8)就是我们要求的结果,而5就是题中的k,2就是结点数与k的模,因此,可以推出一个公式,倒数第k个结点就是按长度为k按分成的若干块中的第二块的第(结点数 % k+ 1)个结点。
    下面来看看(结点数 % k)为0的情况。假设上面的例子中的k为4,正确的输出结果应为9,分块如下:

    1 2 3 4      5 6 7 8      9 10 11 12

    从上面的三个块可以看出,结果正好是最后一个块的第一个结点,这时mod为0(mod=结点数 % k),因此,在这种情况也可以使用上面的公式,只是变成了最后一个块。

    根据上面的基本思想可以设两个指针,p1和p2,其中p1最终指向倒数第2个完整块,p2最终指向倒数第1个完整块,对于第一种情况,p1指向5,p2指向10,这时可以使p1向后移动(k - mod)个结点即可(从5移动3个正好是8)。而对于第二种情况,p1指向8,p2指向12,而mod=0,这时的结果仍然是mod+1,也就是p1向后移动1个结点就是所求的结果。 为了满足(k=结点数)的情况,需要将p1的初始值设为头结点,这样如果(k=结点数),就直接从头结点向后移动一个结点就是最后的结果,如上面的例子求倒数第12个结点,也就是求正数第1个结点。

    下面是这个算法的具体实现(包括核心算法、生成链表及调用核心算法的代码):

public class Test
{

    
static class Node
    {
        
public int data;
        
public Node nextNode;
    }
    
//////////////////////////////////////////
    
//  核心算法
    private static int findNode(Node headNode, int k)
    {
        Node p 
= headNode, p1 = headNode, p2 = null
        
int count = 0;  //  表示结点数
        while (p.nextNode != null)
        {
            p 
= p.nextNode;
            count
++;
            
//  遇到k的整数位个结点,进行分块
            if (count % k == 0)
            {                
                
if (p2 != null)
                    p1 
= p2;
                p2 
= p;
            }
        }
        
//  k超过链表结点数,未找到,返回0
        // 此处也可以用k > count来判断
        if (p2 == null
        {
            
return 0;
        }
        
else
        {
            
int mod = count % k;
            
int offset = mod + 1;  // 任何情况下,最终结果都是p1指向的结点向后移动(mod + 1)个结点
            for (int i = 0; i < offset; i++)
                p1 
= p1.nextNode;
            System.out.println(p1.data);
            
return 1;
        }
    }
    
////////////////////////////////////////
    public static void main(String[] args) throws Exception
    {
        
//产生一个包含1个头结点和120个结点的链表
        Node headNode = new Node();
        Node p 
= headNode;
        
for (int i = 0; i < 120; i++)
        {
            p.nextNode 
= new Node();
            p.nextNode.data 
= i + 1;
            p 
= p.nextNode;
        }
        p.nextNode 
= null;
        
//  开始查找倒数第k个结点,如果找到,返回1,并输出结点的data值
        System.out.println(findNode(headNode, 12));
    }
}

    上面程序的输出结果如下:

    109
    1

    读者也可以使用其他的测试用例来测试上面的程序。

    本算法从空间复杂度O(1)和时间复杂度O(n)的综合指标基本上算是比较优化了,如果哪位读者还有更简单和快速的算法,请跟贴!!




Android开发完全讲义(第2版)(本书版权已输出到台湾)

http://product.dangdang.com/product.aspx?product_id=22741502



Android高薪之路:Android程序员面试宝典 http://book.360buy.com/10970314.html


新浪微博:http://t.sina.com.cn/androidguy   昵称:李宁_Lining

posted on 2009-01-17 20:50 银河使者 阅读(3320) 评论(7)  编辑  收藏 所属分类: javaalgorithm 原创

评论

# re: 09考研数据结构试题的一种解法(Java版)  回复  更多评论   

那么麻烦干嘛。。
一个指针先跑到第k个元素,然后另一个指针从头开始,两个指针同步往后走,直到第一个指针碰到尾部,第二个指针就是倒数第k个位置了。特殊情况(元素个数少于k等)再处理下就行了。
空间复杂度也是O(1)
2009-01-17 22:27 | ZelluX

# re: 09考研数据结构试题的一种解法(Java版)  回复  更多评论   

to ZelluX

这个方法不错,下面是具体的实现代码:

    private static int findNode(Node headNode, int k)
    {       
        Node p1 = headNode, p2 = headNode;
        for(int i = 0; i < k && p2.nextNode != null; i++)
            p2 = p2.nextNode;
        if(p2.nextNode == null) return 0;
        while(p2.nextNode != null)
        {
            p1 = p1.nextNode;
            p2 = p2.nextNode;
        }
        System.out.println(p1.nextNode.data);
        return 1;
    }


2009-01-17 22:59 | 银河使者

# re: 09考研数据结构试题的一种解法(Java版)  回复  更多评论   

我写的空间复杂度是O(N) 时间复杂度是O(1)。直接拿空间换时间。
2009-01-20 08:40 | Zeus2

# re: 09考研数据结构试题的一种解法(Java版)  回复  更多评论   

时间复杂度怎么可能是O(1)呢?至少得移动结点啊,把算法或设计思想贴出来看看
2009-01-20 10:35 | 银河使者

# re: 09考研数据结构试题的一种解法(Java版)  回复  更多评论   

@ZelluX
看了你的说法,有点英雄所见略同的感觉
2009-01-20 20:59 | aaaaaaaa

# re: 09考研数据结构试题的一种解法(Java版)  回复  更多评论   

9494~ZelluX方法最直接,呵呵
2009-01-21 15:29 | 思维时空

# re: 09考研数据结构试题的一种解法(Java版)  回复  更多评论   

ZelluX最好
2009-01-30 20:35 | lichen6928

只有注册用户登录后才能发表评论。


网站导航: