A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

在一个长度为N 的整形数组A里,除了三个数字只出现一次之外,其他的数字都出现了俩次
请写程序输出任意一个只出现一次的数字。程序时间和空间复杂度越小越好
例如:a={1,3,7,9,5,9,4,3,6,1,7}

评分

参与人数 1技术分 +1 收起 理由
唐志兵 + 1 赞一个!

查看全部评分

7 个回复

倒序浏览
本帖最后由 官仁杰 于 2012-9-23 00:41 编辑

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

  2. public class test{
  3.         public static void main(String[] arg){
  4.                 int a[] = {1,3,7,9,5,9,4,3,6,1,7};
  5.                 Arrays.sort(a);
  6.                 for (int i = 0; i < a.length; i++) {
  7.                         boolean flag = false;
  8.                         if(i >0) if(a[i] == a[i-1]) flag =true;
  9.                         if(i<a.length - 1) if(a[i] == a[i+1]) flag = true;
  10.                         if(flag == false)System.out.print(a[i]+ " ");                     
  11.         }
  12.         }
  13. }
复制代码
输出4 5 6  这样算不算?如果想出更好的方案再改

评分

参与人数 2技术分 +1 黑马币 +1 收起 理由
唐志兵 + 1 赞一个!
尤圣回 + 1 赞一个!

查看全部评分

回复 使用道具 举报
我想  中国的 程序员,大部分是很难做出来的!
回复 使用道具 举报
我的算法为:
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])
肯定不能算好,抛砖引玉

评分

参与人数 2技术分 +1 黑马币 +1 收起 理由
滔哥 + 1
尤圣回 + 1 赞一个!

查看全部评分

回复 使用道具 举报
简单一点就是两重循环,并在第二次循环中判断,时间复杂度N^2。

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

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

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

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

  9.                 // 外循环的上限
  10.                 int up = N - 1;
  11.                 for (int i = 1; i < up; ++i) {
  12.                         // 利用集合的特性来去重
  13.                         if (set.contains(a[i])) {
  14.                                 // 包含则删除该元素
  15.                                 set.remove(a[i]);
  16.                         } else {
  17.                                 set.add(a[i]);
  18.                         }
  19.                 }
  20.                 // 随即找到的一个数
  21.                 System.out.println(set.iterator().next());
  22.         }
  23. }
复制代码

评分

参与人数 1技术分 +1 收起 理由
滔哥 + 1

查看全部评分

回复 使用道具 举报
在下刚学了集合,就用集合实现了一下,希望对楼主有所帮助:

/**
*
*  @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:30
7#
以上部分百度者,无分,再次提醒大家,就算不能完整做出来的题目,只要是你自己的想法,回贴说出来,都是可以得到技术分的,而直接百度的,技术分那么离你会很远。
回复 使用道具 举报
滔哥 发表于 2012-9-23 18:09
以上部分百度者,无分,再次提醒大家,就算不能完整做出来的题目,只要是你自己的想法,回贴说出来,都是可 ...

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

点评

加分了,说明,你的答题有效。亲别激动。  发表于 2012-9-23 18:26
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马