黑马程序员技术交流社区

标题: 这题谁会，不要百度，答对了，我向版主申请，给你加技... [打印本页]
作者: 尤圣回    时间: 2012-9-22 23:49
标题: 这题谁会，不要百度，答对了，我向版主申请，给你加技...
在一个长度为N 的整形数组A里，除了三个数字只出现一次之外，其他的数字都出现了俩次
请写程序输出任意一个只出现一次的数字。程序时间和空间复杂度越小越好
例如：a={1,3,7,9,5,9,4,3,6,1,7}
作者: 官仁杰    时间: 2012-9-22 23:55
本帖最后由 官仁杰 于 2012-9-23 00:41 编辑

抛砖引玉，很坑爹的方法，肯定还有更好的
  1. import java.util.Arrays;

  3. public class test{
  4.         public static void main(String[] arg){
  5.                 int a[] = {1,3,7,9,5,9,4,3,6,1,7};
  6.                 Arrays.sort(a);
  7.                 for (int i = 0; i < a.length; i++) {
  8.                         boolean flag = false;
  9.                         if(i >0) if(a[i] == a[i-1]) flag =true;
  10.                         if(i<a.length - 1) if(a[i] == a[i+1]) flag = true;
  11.                         if(flag == false)System.out.print(a[i]+ " ");                     
  12.         }
  13.         }
  14. }
复制代码
输出4 5 6  这样算不算？如果想出更好的方案再改
作者: 黑马杨晨    时间: 2012-9-23 00:12
我想  中国的 程序员，大部分是很难做出来的！
作者: 张小龙    时间: 2012-9-23 08:17
我的算法为：
public class SortTest {
        public static void main(String[] args) {
                int[] a = { 1, 3, 7, 9, 5, 9, 4, 3, 6, 1, 7};
                Arrays.sort(a);   //先将数组排序
                int num = 0;    //用于控制循环的变量
                if (a.length == 1) {
                        System.out.println(a[0]);
                } else if (a.length == 2)
                        System.out.println(a[0]);
                else {while (true) {           //只判断数组长度大于3的情况
                                if (num == a.length - 2) { //循环内最多判断3次
                                        break;
                                }
                                num += 1;
                                if ((a[num] != a[num - 1]) && a[num] != a[num + 1]) {
                                        System.out.print(a[num] + " ");
                                }
                        }
                        if (a[a.length - 1] != a[a.length - 2])   //把最后一个数比较并输出
                                System.out.print(a[a.length - 1]);}}}
总结：循环内最多判断3次，一次if (num == a.length - 2) 另外两次 if ((a[num] != a[num - 1]) && a[num] != a[num + 1])
肯定不能算好，抛砖引玉
作者: 程振    时间: 2012-9-23 12:18
简单一点就是两重循环，并在第二次循环中判断，时间复杂度N^2。

所以需要优化，有两方面:优化外循环和内循环。
外循环至少遍历N-1个元素，然后就是把精力放在优化外循环上

如果有其它方法，外循环可以继续优化，不过不会。。。。

下面是一个示例：
  1. import java.util.HashSet;
  2. import java.util.Set;

  4. public class Demo {
  5.         public static void main(String[] args) {
  6.                 int N = 11;
  7.                 int a[] = { 1, 3, 7, 9, 5, 9, 4, 3, 6, 1, 7 };
  8.                 Set<Integer> set = new HashSet<Integer>();
  9.                 set.add(1);

  11.                 // 外循环的上限
  12.                 int up = N - 1;
  13.                 for (int i = 1; i < up; ++i) {
  14.                         // 利用集合的特性来去重
  15.                         if (set.contains(a[i])) {
  16.                                 // 包含则删除该元素
  17.                                 set.remove(a[i]);
  18.                         } else {
  19.                                 set.add(a[i]);
  20.                         }
  21.                 }
  22.                 // 随即找到的一个数
  23.                 System.out.println(set.iterator().next());
  24.         }
  25. }
复制代码
作者: 张忠豹    时间: 2012-9-23 18:05
在下刚学了集合，就用集合实现了一下，希望对楼主有所帮助：

/**
*
*  @author zhang
        思路：
        因为数字和次数之间存在映射关系，想到了map集合。，
        根据给予的数组，并把数字作为键，去查map集合。
        如果没有对应的值，将该数字作为键。将1作为值存储到map集合中。

        如果有对应的值，将该值取出并自增，将该数字和自增后的结果存储到map集合中。
        这样，键重复出现，新值会覆盖旧值。

        记录了这个数字的最新出现的次数。
        当给定的数组中的数字都遍历完成后，map集中就记录所有数字的次数。
       

        步骤：
        1，定义map集合。
        2，遍历数组。
        3，将遍历到的每一个数字作为键去查map集合。
        4，对通过该键获取到的值进行判断。
*
*/
public class CountDemo {
        public static void main(String[] args) {
                int[] a={1,3,7,9,5,9,4,3,6,1,7};
               
                Map map = getCharCount(a);
               
                Set keys = map.keySet();
                Iterator it = keys.iterator();
                System.out.println("以下的数字出现的次数都是一次：");
                while(it.hasNext()){
                        Integer key = (Integer) it.next();
                        System.out.print(key+"  ");
                }
        }
       
        public static Map getCharCount(int[] str)
        {
                //1,定义map集合。所以使用TreeMap。
                //集合中的键的类型时Integer，值的类型时Integer、
                Map map = new TreeMap();

                int count = 0;
                //2,遍历数组。
                for(int x=0; x<str.length; x++)
                {

                        int in = str[x];
                        //将遍历到的数字作为键，去查map集合中对应的值。
                        Integer value = (Integer)map.get(str[x]);

                        if(value!=null)
                        {
                                count = value;
                        }
                        count++;
                        map.put(str[x],count);

                        count = 0;
                }
               
                return getMaxCount(map);
               
        }
        //获取次数为1的数字
        private static Map getMaxCount(Map map) {
                Set keySet = map.keySet();
                //返回一个包含此 set 中所有元素的数组；返回数组的运行时类型是指定数组的类型
                Integer[] arr = (Integer[]) keySet.toArray(new Integer[keySet.size()]);
                Map valueMap = new TreeMap();
                Integer min =1;  
                for (int ii=0;ii<arr.length;ii++) {
                        if((Integer)map.get(arr[ii])==min) {
                                Integer key = arr[ii];
                                Integer value = (Integer)map.get(arr[ii]);
                                valueMap.put(key, value);
                        }
                }
                return  valueMap;
        }
}

输出的结果为：

以下的数字出现的次数都是一次：
4  5  6  
作者: 滔哥    时间: 2012-9-23 18:09
以上部分百度者，无分，再次提醒大家，就算不能完整做出来的题目，只要是你自己的想法，回贴说出来，都是可以得到技术分的，而直接百度的，技术分那么离你会很远。
作者: 张小龙    时间: 2012-9-23 18:11
滔哥 发表于 2012-9-23 18:09
以上部分百度者，无分，再次提醒大家，就算不能完整做出来的题目，只要是你自己的想法，回贴说出来，都是可 ...

涛哥 百度死XX啊 我可是一个字都没有百度过



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2