讨论一个算法

flw

原帖由 uclinux_arm9 于 2007-3-20 21:38 发表

上机测试一下　这个是答案

楼主说的是 N 个整数，不是 N 个 10 以内的整数。
你这个程序不能处理超过 10 的整数。

gxglhyy

原帖由 lenovo 于 2007-3-20 17:45 发表

刚才想了想，能不能找到这个问题的O（n）的算法，
最后可以归结到能不能找到O（n）的排序算法。
像基数排序，此外还有桶、箱排序都是O（n）的，
但它们都有一些限制。

这个问题和排序是有点区别点：这组数中只有一对是相同的，其他的都不同

飞灰橙

32位的整数？
等俺装上了64位机，内存条便宜的像馒头一样时候，
问题迎刃而解

飞灰橙

呵呵，上面是笑话，
这个问题有点像脑筋急转弯，绝对有解，大家不觉得吗？

lenovo

原帖由 gxglhyy 于 2007-3-20 23:22 发表


这个问题和排序是有点区别点：这组数中只有一对是相同的，其他的都不同

不过这个和解决问题的思路有关系吗？

redhat008

原帖由 cobras 于 2007-3-20 17:34 发表
最少需求是2^(32-3)=2^29字节=512MB
所以n只能是有限集

你的意思是不是？？
使用位向量，对于一般的有限非负整数集是可以解决的

blackuhlan

这个是网上找到的一个hashtable地实现
/** * Introduction to Algorithms, Second Edition
* 11.4  Open addressing tables * @author 土豆爸爸 *  */
public class HashTable {
          /**     * 数据节点     */
    public static class Node {
            int key;
            public Node(int key) {
            this.key = key;
        }
    }
    private Node[] table; //直接寻址表
    private Node deleted = new Node(0);
    /**     * 构造函数。     * @param size 表大小     */
    public HashTable(int size)
    {
        table = new Node[size];
    }
    /**
     * 根据键值k查找节点。需要跳过标记为deleted的位置
     * @param k 节点的键值
     * @return 键值为k的节点，未找到返回null
     */
     public Node search(int k)
     {
         for(int i = 0; i < table.length;i++)
         {
         int j = hash(k, i);
         if(table[j] == null) {
            return null;
         } else if(table[j] != deleted && table[j].key == k) {
            return table[j];
            }
         }
         return null;
    }
    /**
    * 插入节点x。根据x.key计算哈希值，如果哈希值对应的位置
    * 已被占据,查找下一个,直到找到一个空位或标记为deleted的位置。
    * @param x 待插入节点
    */
    public void insert(Node x) {
        for(int i = 0; i < table.length;i++)
        {
            int j = hash(x.key, i);
            if(table[j] == deleted || table[j] == null) {
               table[j] = x;
               return;
            }
        }
        throw new RuntimeException("Over flow");
    }
    /**
    * 删除节点x。将删除节点标记为deleted。
    * @param x 待删除节点
    */
    public void delete(Node x) {
        for(int i = 0; i < table.length;i++) {
            int j = hash(x.key, i);
            if(table[j] == x) {
                table[j] = deleted;
                break;
            }
        }
    }
    /**
    * 计算哈希值
    * @param key 键值
    * @return 哈希值
    */
    private int hash(int key, int i) {
        int m = table.length;
        return (key % m + i) % m;
    }
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < table.length; i++) {
            if (table[i] == null) {
            sb.append("null\t");
            } else {
                sb.append(table[i].key).append("\t");
            }
        }
        return sb.toString();
    }
}
    import junit.framework.TestCase;
    public class HashTableTest extends TestCase
    {
        public void testLinkedList() {
            HashTable table = new HashTable(100);
            // 插入100个随机节点
            for (int i = 0; i < 100; i++) {
                int key = (int) (Math.random() * 1000);
                if (table.search(key) == null) {
                    table.insert(new HashTable.Node(key));
                }
            }
            System.out.println(table);
            // 找到一个节点
            HashTable.Node node = null;
            for (int i = 0; i < 100; i++) {
                node = table.search(i);
                if (node != null) {
                    break;
                }
            }
            assertNotNull(node);
            table.delete(node);
            assertEquals(null, table.search(node.key));
        }
    }

blackuhlan

我在6楼写的回复不是一个好的算法，时间复杂度为O(n)的话，可以用刚才谁说到的，开一个大小为n的数组，计算每个数出现的次数，当某个数出现到第二次时就是结果咯

datuhao

我咋看这个题目这么眼熟呢?
出这个题目的人一定非常迷恋位图排序算法.
见<编程珠玑>第1章,第1节
题目说了,全是整数,我觉得位图排序算法是最完美的解决方案

tsgx8848

原帖由 A.com 于 2007-3-20 19:15 发表
顺序读取整数并根据其值放入数组（n，n），当读取的整数其位置已被占用时，相同值就找出来了。

正解！！