`
yunchow
  • 浏览: 323651 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

找出序列中不重复的元素

阅读更多
阿里的一个面试题:
一个序列里除了一个元素,其他元素都会重复出现3次,设计一个时间复杂度与空间复杂度最低的算法,找出这个不重复的元素。

实现如下:


package bitmap;

import java.util.BitSet;

public class BitMapMain {

	static int[] list = {2, 3, 6, 3, 2, 5, 3, 2, 6, 6, 9, 9, 7, 7};
	
	public static void main(String[] args) {
		int len = list.length * 2;
		BitSet bs = new BitSet(len);
		
		for (int i = 0; i < list.length; i++) {
			int n = 2 * list[i];
			boolean b1 = bs.get(n);
			boolean b2 = bs.get(n + 1);
			if (!b1 && !b2) { // 00
				bs.set(n, true);
				bs.set(n + 1, false);
			}
			else if (b1 && !b2) { // 01
				bs.set(n + 1, true);
				bs.set(n, false);
			}
			else if (!b1 && b2) { // 10
				bs.set(n, n + 1, true);
			}
		}
		for (int i = 0; i < bs.length(); i += 2) {
			boolean b1 = bs.get(i);
			boolean b2 = bs.get(i + 1);
			if (!b1 && !b2) { // 00
				// 0次
			}
			else if (b1 && !b2) { // 01
				System.out.println(i / 2 + "一次");
			}
			else if (!b1 && b2) { // 10
				System.out.println(i / 2 + "两次");
			}
			else if (b1 && b2) { // 10
				System.out.println(i / 2 + "三次");
			}
		}
	}

}


3
1
分享到:
评论
9 楼 113.com 2014-09-23  
113.com 写道
jag522 写道
113.com 写道
jag522 写道
113.com 写道
很巧妙使用二叉树原理。厉害

跟二叉树没什么关系吧。。00表示0次,01表示1次,10表示2次,11表示3次


有很大关系好不,你看用这个就只能算最多出现2n-1三次的,如要算最多出现5次要用三叉树,如果最多出现7次要四叉,以此类推。你没看清这算法其中的本质。


如果要算最多重复出现4~7次的,则需要3位bit来存储;如果8~15次,则需要4位bit来存储。而树有叶子节点等概念,跟这个场景没什么太大关系啊。


你只见过三叉树啊,我说的是树,三叉四叉五叉。反正我试了用三位只能算出最多五个重复的,不知道你怎么能最多算出7次。付上代码
:package bitmap; 
 
import java.util.BitSet; 
 
public class BitThreeMapMain { 
 
    static int[] list = {2, 3, 6, 3, 2, 5, 3, 2, 6, 9, 9, 7,7,7,7,7,9,9}; 
     
    public static void main(String[] args) { 
        int len =list.length * 3; 
        BitSet bs = new BitSet(len); 
         
        for (int i = 0; i < list.length; i++) { 
            int n = 3 * list[i]; 
            boolean b0 = bs.get(n - 1); 
            boolean b1 = bs.get(n); 
            boolean b2 = bs.get(n + 1); 
            if (!b0&&!b1 && !b2) { // 000 
                bs.set(n-1, true);
                bs.set(n, false); 
                bs.set(n + 1, false); 
            } 
            if (b0&&!b1 && !b2) { // 100 
                bs.set(n-1, false);
                bs.set(n, true); 
                bs.set(n + 1, false); 
            } 
            if (!b0&&b1 && !b2) { // 010 
                bs.set(n-1, false);
                bs.set(n, false); 
                bs.set(n + 1, true); 
            } 
            if (!b0&&!b1 && b2) { // 001 
                bs.set(n-1, true);
                bs.set(n, true); 
                bs.set(n + 1, false); 
            } 
           
            if (b0&&b1 && !b2) { // 110 
                bs.set(n-1, true);
                bs.set(n, false); 
                bs.set(n + 1, true); 
            } 
            if (b0&&!b1 && b2) { // 101 
                bs.set(n-1,n + 1, true); 
              
            } 
           
        } 
        System.out.println(bs.length());
        for (int i = 3; i < bs.length(); i += 3) { 
        boolean b0 = bs.get(i-1); 
            boolean b1 = bs.get(i); 
            boolean b2 = bs.get(i + 1); 
      
            if (!b0&&!b1 && !b2) { // 000 
            // 0次 
            } 
            if (b0&&!b1 && !b2) { // 100 
            System.out.println(i / 3 + "=1次"); 
            } 
            if (!b0&&b1 && !b2) { // 010 
            System.out.println(i / 3 + "=2次");  
            } 
            if (!b0&&!b1 && b2) { // 001 
            System.out.println(i / 3 + "=3次"); 
            } 
           
            if (b0&&b1 && !b2) { // 110 
            System.out.println(i / 3 + "=4次"); 
            } 
            if (b0&&!b1 && b2) { // 101 
            System.out.println(i / 3 + "=5次"); 
              
            } 
           
        } 
    } 
 



哦,是的,你是对的。是2^n次冥关系。我还写少了两种。但真的可以抽象成一个多叉树来算。
8 楼 113.com 2014-09-23  
jag522 写道
113.com 写道
jag522 写道
113.com 写道
很巧妙使用二叉树原理。厉害

跟二叉树没什么关系吧。。00表示0次,01表示1次,10表示2次,11表示3次


有很大关系好不,你看用这个就只能算最多出现2n-1三次的,如要算最多出现5次要用三叉树,如果最多出现7次要四叉,以此类推。你没看清这算法其中的本质。


如果要算最多重复出现4~7次的,则需要3位bit来存储;如果8~15次,则需要4位bit来存储。而树有叶子节点等概念,跟这个场景没什么太大关系啊。


你只见过三叉树啊,我说的是树,三叉四叉五叉。反正我试了用三位只能算出最多五个重复的,不知道你怎么能最多算出7次。付上代码
:package bitmap; 
 
import java.util.BitSet; 
 
public class BitThreeMapMain { 
 
    static int[] list = {2, 3, 6, 3, 2, 5, 3, 2, 6, 9, 9, 7,7,7,7,7,9,9}; 
     
    public static void main(String[] args) { 
        int len =list.length * 3; 
        BitSet bs = new BitSet(len); 
         
        for (int i = 0; i < list.length; i++) { 
            int n = 3 * list[i]; 
            boolean b0 = bs.get(n - 1); 
            boolean b1 = bs.get(n); 
            boolean b2 = bs.get(n + 1); 
            if (!b0&&!b1 && !b2) { // 000 
                bs.set(n-1, true);
                bs.set(n, false); 
                bs.set(n + 1, false); 
            } 
            if (b0&&!b1 && !b2) { // 100 
                bs.set(n-1, false);
                bs.set(n, true); 
                bs.set(n + 1, false); 
            } 
            if (!b0&&b1 && !b2) { // 010 
                bs.set(n-1, false);
                bs.set(n, false); 
                bs.set(n + 1, true); 
            } 
            if (!b0&&!b1 && b2) { // 001 
                bs.set(n-1, true);
                bs.set(n, true); 
                bs.set(n + 1, false); 
            } 
           
            if (b0&&b1 && !b2) { // 110 
                bs.set(n-1, true);
                bs.set(n, false); 
                bs.set(n + 1, true); 
            } 
            if (b0&&!b1 && b2) { // 101 
                bs.set(n-1,n + 1, true); 
              
            } 
           
        } 
        System.out.println(bs.length());
        for (int i = 3; i < bs.length(); i += 3) { 
        boolean b0 = bs.get(i-1); 
            boolean b1 = bs.get(i); 
            boolean b2 = bs.get(i + 1); 
      
            if (!b0&&!b1 && !b2) { // 000 
            // 0次 
            } 
            if (b0&&!b1 && !b2) { // 100 
            System.out.println(i / 3 + "=1次"); 
            } 
            if (!b0&&b1 && !b2) { // 010 
            System.out.println(i / 3 + "=2次");  
            } 
            if (!b0&&!b1 && b2) { // 001 
            System.out.println(i / 3 + "=3次"); 
            } 
           
            if (b0&&b1 && !b2) { // 110 
            System.out.println(i / 3 + "=4次"); 
            } 
            if (b0&&!b1 && b2) { // 101 
            System.out.println(i / 3 + "=5次"); 
              
            } 
           
        } 
    } 
 

7 楼 jag522 2014-09-23  
113.com 写道
jag522 写道
113.com 写道
很巧妙使用二叉树原理。厉害

跟二叉树没什么关系吧。。00表示0次,01表示1次,10表示2次,11表示3次


有很大关系好不,你看用这个就只能算最多出现2n-1三次的,如要算最多出现5次要用三叉树,如果最多出现7次要四叉,以此类推。你没看清这算法其中的本质。


如果要算最多重复出现4~7次的,则需要3位bit来存储;如果8~15次,则需要4位bit来存储。而树有叶子节点等概念,跟这个场景没什么太大关系啊。
6 楼 yunchow 2014-09-23  
113.com 写道
jag522 写道
113.com 写道
很巧妙使用二叉树原理。厉害

跟二叉树没什么关系吧。。00表示0次,01表示1次,10表示2次,11表示3次


有很大关系好不,你看用这个就只能算最多出现2n-1三次的,如要算最多出现5次要用三叉树,如果最多出现7次要四叉,以此类推。你没看清这算法其中的本质。


是不是log2n呢,所以应该是二叉树的深度,而不是n叉树吧
5 楼 113.com 2014-09-23  
jag522 写道
113.com 写道
很巧妙使用二叉树原理。厉害

跟二叉树没什么关系吧。。00表示0次,01表示1次,10表示2次,11表示3次


有很大关系好不,你看用这个就只能算最多出现2n-1三次的,如要算最多出现5次要用三叉树,如果最多出现7次要四叉,以此类推。你没看清这算法其中的本质。
4 楼 jag522 2014-09-22  
113.com 写道
很巧妙使用二叉树原理。厉害

跟二叉树没什么关系吧。。00表示0次,01表示1次,10表示2次,11表示3次
3 楼 yunchow 2014-09-22  
113.com 写道
很巧妙使用二叉树原理。厉害

这。。好像没有二叉树的原理吧,只是位图的原理,两位来存重复的次数,时间复杂度为n
2 楼 113.com 2014-09-18  
很巧妙使用二叉树原理。厉害
1 楼 pi88dian88 2014-09-18  
 

相关推荐

    算法:求第k小元素

    首先,取数组的第一个、最后一个和中间元素,找出三个中最小的作为新的枢轴,然后根据枢轴的位置将数组分为三部分:小于枢轴、等于枢轴和大于枢轴。如果k在小于枢轴的区间,就在这个区间重复此过程;如果k在大于枢轴...

    用分治法实现元素选择

    在这个特定的问题中,我们要利用分治法来实现“元素选择”,即找出线性序列集中第k小的元素及其位置。下面我们将深入探讨这个过程。 首先,理解问题的关键在于如何有效地比较并排序序列中的元素。分治法的基本步骤...

    重复元素全排列

    这种算法常用于密码学、数据加密以及计算机科学中的各种组合优化问题,例如在处理含有重复字母的字符串时,找出所有可能的重组方式。 #### 知识点二:算法实现原理 在Java中实现重复元素全排列,通常采用递归的...

    最长不减子序列

    总结来说,最长不减子序列问题是一个典型的动态规划问题,通过维护一个动态规划数组,可以有效地找出给定序列的最长不减子序列的长度。这种思想在解决许多其他序列相关的优化问题时也非常有用,比如最长递增子序列、...

    动态规划最长子序列

    该算法的目标是找出两个序列中的最长公共子序列,即一个序列中存在但不一定是连续的子序列,同时这个子序列也是另一个序列的子序列。LCS 不考虑子序列在原序列中的相对位置,只关注它们的元素。 动态规划方法是解决...

    最长递增子序列问题

    最长递增子序列...总结来说,最长递增子序列问题是一个经典的动态规划问题,通过维护一个动态规划数组来找出序列中的最长递增子序列。理解并熟练掌握这种问题的解决方法对于提升算法设计和编程能力非常有帮助。

    《奇异序列》

    奇异序列是一种特殊的数字序列,其特点可能包含但不限于以下几点:每个元素是前两个或前若干个元素的某种组合(如求和、乘积等)、序列中特定位置的元素遵循特定规律或者序列本身具有某种数学上的奇特性质。...

    最长公共子序列

    该问题旨在找到两个序列(通常是字符串)的最长子序列,这个子序列不需要在原序列中连续出现,但必须保持原有顺序。在本问题中,我们有两个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},目标是找到它们的LCS。 解决LCS...

    js代码-数组的最大不重复连续子序列

    在JavaScript编程中,"数组的最大不重复连续子序列"是一个常见的算法问题,它涉及到数组处理、动态规划或者滑动窗口等技术。这个问题的目标是从给定的数组中找到一个最长的子序列,这个子序列中的元素既不重复且是...

    JavaScript实现找出数组中最长的连续数字序列

    关于如何用JavaScript实现找出数组中最长的连续数字序列,以下是一些重要的知识点。 首先,需要理解连续数字序列的定义:在一个整数序列中,连续数字是指按数值顺序排列,且数值相邻的数字序列。例如,序列[1, 2, 3...

    最长子序列详解

    这个代码首先初始化了 `dp` 数组,然后通过两层循环找出所有可能的子序列,根据元素之间的大小关系更新子序列长度。最后返回最长子序列的长度。 **总结:** 最长子序列问题是一个典型的动态规划问题,适用于解决一...

    序列模式GSP算法

    其核心定义是给定一个由不同序列组成的集合,序列中的每个元素由不同项目按顺序组成,并且给定一个最小支持度阈值,序列模式挖掘的目标是找出所有在序列集中出现频率不低于该最小支持度阈值的频繁子序列。...

    动态规划算法中对子序列的一些模板

    - LIS问题是在一个序列中找出最长的严格递增子序列。 - 动态规划解法:dp[i]表示以第i个元素结尾的LIS的长度。状态转移方程为dp[i] = max(dp[j] + 1),其中j 且nums[j] [i]。 - 输出位置:可以使用单调栈或二分...

    基于动态规划的序列比对

    设定一个固定长度的窗口,滑动并比对每个可能的子序列,找出与目标序列得分最高的子序列,这就是所谓的局部比对。 在MFC(Microsoft Foundation Classes)环境中实现这样的程序,需要利用MFC的事件驱动模型和控件来...

    多个数组中的元素集合到一个数组中并输出

    `Union()`方法也是LINQ的一部分,用于返回两个序列的唯一元素集合并删除重复项。在这个场景下,如果数组元素有重复,它会自动去除。但如果数组元素无重复,`Union()`等同于`Concat()`。 ```csharp int[] ...

    头歌c语言实验之最长特殊序列.zip

    我们的任务是找出这样的序列中最长的一个。 在C语言中解决这个问题,我们需要利用字符串处理函数,如`strlen()`来获取字符串长度,`strcpy()`和`strcat()`来复制和连接字符串,以及指针来遍历字符串。但关键在于...

    线性选择排序算法 算法作业的线性选择排序 算法作业的线性选择排序

    这是因为每个元素都需要与其他所有元素比较一次,以找出最小的元素。因此,尽管线性选择排序的实现相对简单,但在处理大量数据时效率较低,通常不推荐在实际应用中使用。对于大数据集,更高效的排序算法如快速排序、...

    动态规划求最长公共子序列

    最长公共子序列是指两个序列中存在的一段序列,它既出现在第一个序列中,也出现在第二个序列中,但不考虑元素的相对顺序。例如,"ABCDGH"和"AEDFHR"的最长公共子序列是"ADH"。 在给定的代码中,`LCSLength`函数用于...

    算法之动态规划---单调递增子序列

    4. **结果获取**:遍历`dp`数组,找出其中的最大值即为最长递增子序列的长度。 #### Java实现示例: ```java public class LongestIncreasingSubsequence { public int lengthOfLIS(int[] nums) { if (nums == ...

Global site tag (gtag.js) - Google Analytics