精华内容
下载资源
问答
  • 出1到n中重复的数字

    千次阅读 2018-08-02 16:22:46
    在数组nums[n + 1]中,数字都是1到n范围内的,那么至少有一个重复数字,找到它。 分析: 这其实是一道比较简单的算法题,但是,如果是面试题,面试官除了用时间复杂度和空间复杂度来约束你...

    背景:

    很早以前在CSDN中MoreWindows的白话算法中看到,以为那个就是最佳的方法,后来在LeetCode中做到,再后来在和同学讨论中又深化了一下。

    一道很经典的题目,算法无止境。

    题目:

    在数组nums[n + 1]中,数字都是1到n范围内的,那么至少有一个重复数字,找到它。

    分析:

    这其实是一道比较简单的算法题,但是,如果是面试题,面试官除了用时间复杂度和空间复杂度来约束你之后,还可能要求不能移动或改动数组(前者不能swap或sort,后者不能更改值)。这才是这道题的难点。所以接下来,我就用时间复杂度、空间复杂度,是否移动,是否改动原数组四个维度来判断算法。

    并且希望大家看到这里的时候停顿一下,思考过后再看,不要直接看答案,这样是浪费了一道好题目。

    方法1:

    哈希:另外开创一个数组hash[],大小为n + 1,初始值都为0。因为原数组范围都在1到n内,所以我们可以直接通过对相应的位置上的hash[nums[i]]++来标志。

    通过判断当前的hash[nums[i]]是否为0就可以知道其是否是重复的数字。

    时间复杂度O(n),空间复杂度O(n),不用移动原数组,不用改动原数组。

    代码如下:

    int findDuplicate1(vector<int> nums) {
    	vector<int>hash(nums.size() + 1);
    	for (auto i : nums){
    		if (hash[i] == 0)
    			hash[i] ++;
    		else
    			return i;
    	}
    }
    
    


    方法2:

    排序:排序也是比较容易想到的方法,其实排序可以针对范围不止在1到n的数字。(这在另一方面就说明了排序的算法拓展了题目中的条件,所以是没有充分利用题目的条件,当然也就很难成为最优)

    时间复杂度O(nlogn),空间复杂度O(1),需要移动原数组,不用改动原数组。

    代码如下:

    
    int findDuplicate2(vector<int> nums) {
         sort(nums.begin(), nums.end());
         for (int i = 1; i < nums.size(); ++i){
          if (nums[i] == nums[i - 1])
           return nums[i];
         }
    }
    


     

    方法3:

    类基数排序:如果当前的数字不等于当前的位置,就把当前数字换到其对应的位置上去,然后依次类推,直到找到重复的元素为止。

    相应的方法可以看:http://blog.csdn.net/morewindows/article/details/8204460

    我这里举个栗子:比如对于nums为数组 [2, 4, 8, 5, 7, 6, 1, 9, 3, 2] 的情况。

    nums[0]的位置是2,把2和它本来的位置上的数字nums[1]调换得到:[4, 2, 8, 5, 7, 6, 1, 9, 3, 2]

    nums[0]的位置是4,把4和它本来的位置上的数字nums[3]调换得到:[5, 2, 8, 4, 7, 6, 1, 9, 3, 2]

    nums[0]的位置是5,把5和它本来的位置上的数字nums[4]调换得到:[7, 2, 8, 4, 5, 6, 1, 9, 3, 2]

    nums[0]的位置是7,把7和它本来的位置上的数字nums[6]调换得到:[1, 2, 8, 4, 5, 6, 7, 9, 3, 2]

    nums[0]的位置是1,刚好!那么就不用调换,前进。

    nums[1]的位置是2,刚好!那么就不用调换,前进。

    nums[2]的位置是8,把8和它本来的位置上的数字nums[7]调换得到:[1, 2, 9, 4, 5, 6, 7, 8, 3, 2]

    nums[2]的位置是9,把9和它本来的位置上的数字nums[8]调换得到:[1, 2, 3, 4, 5, 6, 7, 8, 9, 2]

    nums[2]的位置是3,刚好!那么就不用调换,前进。

    nums[3]的位置是4,刚好!那么就不用调换,前进。

    nums[4]的位置是5,刚好!那么就不用调换,前进。

    nums[5]的位置是6,刚好!那么就不用调换,前进。

    nums[6]的位置是7,刚好!那么就不用调换,前进。

    nums[7]的位置是8,刚好!那么就不用调换,前进。

    nums[8]的位置是9,刚好!那么就不用调换,前进。

    nums[9]的位置是2,而2的位置nums[1]上已经是2了,所以就找到了重复元素2。

    时间复杂度O(n),空间复杂度O(1),需要移动原数组,不用改动原数组。

    代码如下:

    int findDuplicate3(vector<int> nums) {
    	int n = nums.size();
    	for (int i = 0; i < n; ++i){
    		while (i != nums[i] - 1){
    			if (nums[i] == nums[nums[i] - 1])
    				return nums[i];
    			swap(nums[i], nums[nums[i] - 1]);
    		}
    	}
    	return -1;
    }
    


    方法4:

    标记法:我们可以看到,其实在nums[n + 1]中,因为数字都是在1到n之内,所以nums[i]就像一个个指针,指着另外的位置上的数字。

    有一个巧妙的办法是,我们遍历一遍数字,把nums[i]指向的数(即nums[nums[i]])做一个+n的操作,那么如果遇到一个nums[nums[i]]的值已经大于n了,说明这个数已经被其他数字指到过了,也就是找到了重复值。在执行的过程中,我们还要先判断一下nums[i]是否大于n(因为可能先前被别人指过所以+n了),用一个值来保存其原来的值。

    具体的思路参考:http://blog.csdn.net/morewindows/article/details/8212446

    时间复杂度O(n),空间复杂度O(1),不用移动原数组,需要改动原数组。

    代码如下:

    
    int findDuplicate4(vector<int> nums) {
    	int n = nums.size();
    	for (int i = 0; i < n; ++i){
    		int next = nums[i] - 1;
    		if (nums[i] > n)
    			next -= n;
    		if (nums[next] > n)
    			return next + 1;
    		else
    			nums[next] += n;
    	}
    	return -1;
    


    方法5:(举一反三,适合教程)

     

    二分搜索法:二分搜索其实是个很神奇的东西,用的好可以举一反三用在各种地方,其实,关键就是你把left和right当做是哪里的值,一般人都只是把这两个当做是数组中的min和max(在本题1和n),或者是数组中的头尾(本题中的nums[0]和nums[n])。所以,适用不了。

    其实,换个思路,我们只要把left和right当做是ans的下上界限就能别有洞天。接着开展二分搜索中的搜索过程:mid取中值,那么nums中的数就被分成了[left - mid - right]两端了。

    然后我们遍历一遍nums,统计所有<=mid的值count,如果left + count > mid + 1,说明[ left - mid ]段的数字中存在重复(ans为其区间的值),所以令right = mid。

    反之就是[ mid - right ]的数字,所以令left = mid + 1;

    知道其结束条件即可。

    时间复杂度O(nlogn),空间复杂度O(1),不用移动原数组,不用改动原数组。

    代码如下:

    int findDuplicate5(vector<int> nums) {
    	int n = nums.size();
    	int left = 1, right = n;
    	int mid, count;
    	while (left < right)
    	{
    		count = 0;
    		mid = (left + right) / 2;
    		for (int i = 0; i < n; ++i)
    		{
    			if (nums[i] >= left && nums[i] <= mid)
    				++count;
    		}
    		if (left + count > mid + 1)
    			right = mid;
    		else
    			left = mid + 1;
    	}
    	return left;
    }
    


     

    方法6:(最佳)

     

    链表找环法:首先,我们来复习一下链表找环:参考:http://blog.csdn.net/xudacheng06/article/details/7706245

    有一个链表,要确定其中是否有环,以及环的入口:

    寻找环的入口点: 

    设置两个步长的指针:fast和slow,初始值都设置为头指针。其中fast每次2步,slow每次一步,发现fast和slow重合,确定了单向链表有环路。接下来,让fast回到链表的头部,重新走,每次步长1,那么当fast和slow再次相遇的时候,就是环路的入口了。

    证明:在fast和slow第一次相遇的时候,假定slow走了n步,环路的入口是在p步,那么
               slow走的路径: p+c = n; c为fast和slow相交点 距离环路入口的距离
               fast走的路径: p+c+k*L = 2*n; L为环路的周长,k是整数
              显然,如果从p+c点开始,slow再走n步的话,还可以回到p+c这个点。
              同时,fast从头开始走,步长为1,经过n步,也会达到p+c这点。
              显然,在这个过程中fast和slow只有前p步骤走的路径不同。所以当p1和p2再次重合的时候,必然是在链表的环路入口点上。

    请仔细理解上面这一段话,必要时自己画一画。

    那么重点是:为什么本题能抽象为一个链表找环的问题?一定会有环的存在吗?一定会有环外的p的部分吗?

    我们先来看[2, 4, 8, 5, 7, 6, 1, 9, 3, 2] 的栗子,

    其中,如果按照2指向的是nums[1]即为4这样的思路:它们形成的图如下:

    其中,因为每个数字都会指向其他数字,或指向自己,所以可能会有多个环或一个环,并且因为有重复数字,所以它所占的位置会被别人多次指到,相当于多了圆环中的两个节点的部分,所以它会是有一个把手突出,并且因为有0这个位置 ,但是没有0这个元素,所以一定会有从0开始的环外p部分。

    以上几点说明,在本题是一定会形成带把手的环的形状,并且环的起点就是重复的元素。

    时间复杂度O(n),空间复杂度O(1),不用移动原数组,不用改动原数组。

    代码如下:

    int findDuplicate6(vector<int> nums) {
    	int slow = 0;
    	int fast = 0;
    	do{
    		slow = nums[slow];
    		fast = nums[nums[fast]];
    	} while (slow != fast);
    	fast = 0;
    	while (fast != slow){
    		fast = nums[fast];
    		slow = nums[slow];
    	}
    	return fast;
    }
    

     

    方法7:(适用于只有一个重复元素且只重复一次的情况)

     

    数学平方和法:如果题目中重复元素只重复一次的话,或者改一下题目,对于nums[n],有一个数字没有出现,还有一个数字重复。我们还可以用数学的方法来解决。

    不妨设消失的数字为a,重复的数字为b。我们的思路是找到两个二元方程,就可以解出a和b。

    如果按照原本的数字排列,有其总和为1+2+...+n = n*(1+n)/2。

    有其平方和为1^2+2^2+...+n^2 = n*(n+1)*(2*n+1)/6。

    现在的总和为1+2+...+n-a+b,

    现在的平方和为1^2+2^2+...+n^2-a^2+b^2。

    所以可以计算出a和b。

    时间复杂度O(n),空间复杂度O(1),不用移动原数组,不用改动原数组。

    代码如下:

    int findDuplicate7(vector<int> nums) {//适用于只有一个重复元素,且该元素只重复一次
    	int n = nums.size();
    	int sum = 0;//sum of ni now
    	int sum2 = 0;//sum of ni^2 now
    	int origSum = (1 + n) * n / 2;//sum of (1+2+...+n)
    	int origSum2 = n * (n + 1) * (2 * n + 1) / 6;//sum of (1^2+2^2+...+n^2)
    	for (auto i : nums){
    		sum += i;
    		sum2 += i * i;
    	}
    	//a is the missing number, b is the duplicate number
    	int a2minusb2 = origSum2 - sum2;
    	int aminusb = origSum - sum;
    	int aplusb = a2minusb2 / aminusb;
    	int b = (aplusb - aminusb) / 2;
    	return b;
    }
    



     

    结果截图:

     

    参考资料:

    其中方法3,4参考MoreWindows:

    http://blog.csdn.net/morewindows/article/details/8204460

    和http://blog.csdn.net/morewindows/article/details/8212446

    方法5,6参考LeetCode的Discuss:

    https://leetcode.com/discuss/questions/oj/find-the-duplicate-number

    链表找环的参考:http://blog.csdn.net/xudacheng06/article/details/7706245

    展开全文
  • java 出小于数字N的所有素数

    千次阅读 2017-04-25 21:01:00
    java出小于数字N的所有素数

    代码如下所示:

    package test3;
    
    import java.util.Scanner;
    
    /**
     * 找出小于数字N的所有素数(工程师)
     * @author saicy(博客 http://blog.csdn.net/sai739295732)
     */
    public class test5 {
    	public static void main(String[] args) {
    		Scanner scan = new Scanner(System.in);
            int n = scan.nextInt();
    		for(int i=1;i<=n;i++){
    			if(isPrime(i)){
    				System.out.println(i);
    			}
    		}
    	}
    	public static boolean isPrime(int a) {  
            boolean flag = true;  
            // 素数不小于2  质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数的数称为质数。
            if (a < 2) {
                return false;  
            } else {  
                for (int i = 2; i <= Math.sqrt(a); i++) {
                	// 若能被整除,则说明不是素数,返回false 
                    if (a % i == 0) { 
                        flag = false;  
                        break;// 跳出循环  
                    }  
                }  
            }  
            return flag;  
        }  
    }

    输入:6

    输出结果:


    展开全文
  • 建立个数为m的最小堆,然后遍历n维护这个最小堆就可以了,算法的时间复杂度是n*log(m)。还是比较高效的算法的。 今天我又发现了一种解决方法,那就是STL里面的一种算法,STL里面的nth_element就是这样的一种...

    分析:这个问题,我之前遇到的时候想到的解决方案是,最小堆解决方法。建立个数为m的最小堆,然后遍历n维护这个最小堆就可以了,算法的时间复杂度是n*log(m)。还是比较高效的算法的。


    今天我又发现了一种解决方法,那就是STL里面的一种算法,STL里面的nth_element就是这样的一种算法。利用类似于快速排序的过程,找到前面的m个最大的数字。


    不多说了,看代码吧。通过代码可以看出,和快排基本相似。


    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    //在m个数中寻找最大的n个数
    //将数组M[m]中的最大的n(n<m)个数放在数组前面
    void search(int M[], int m, int n)
    {
        if (n >= m) return;
        int t = M[0];
        int i = 0, j = m - 1;
        while (i < j) {
            while (i < j && M[j] < t) --j;
            if (i < j) M[i++] = M[j];
    
            while (i < j && M[i] >= t) ++i;
            if (i < j) M[j--] = M[i];
        }
        M[i] = t;
        if (i < n) {
            search(&M[i+1], m - i - 1, n - i - 1);
        } else if (i > n) {
            search(M, i, n);
        }
        return;
    }
    
    void test()
    {
        int M[] = {8, 3, 9, 0, 4, 2, 5, 7, 1, 6};
        int m = 10, n = 6;
    
        printf("原始数据:");
        for(int i =  0; i < m; ++i)
            printf("%d ", M[i]);
        printf("\n");
    
        search(M, m, n);
    
        printf("结果数据:");
        for(int i = 0; i < n; ++i)
            printf("%d ", M[i]);
        printf("\n");
    }
    
    int main()
    {
        test();
        return 0;
    }
    


    展开全文
  • 分析:连续的正整数表示至少有两个数字,所以最多有(1+n)/2个连续的序列,这就表示可以循环(1+n)/2次且这也是最大数字。 下面就是我的实现过程: public static void getSubInteger(int n){ //最多有max个...

    看到一面试题,感觉挺有意思的就思考写了一下,记录当时的思路。
    分析:连续的正整数表示至少有两个数字,所以最多有(1+n)/2个连续的序列,这就表示可以循环(1+n)/2次且这也是最大数字。
    下面就是我的实现过程:

    public static void getSubInteger(int n){
      //最多有max个数字
      int max = (n + 1) / 2;
      //记录有多少种连续的数
      int num = 0;
      for (int i = 1; i <= max; i++) {
       int sum = 0;
       for (int j = i; j <= max; j++) {
        sum += j;
        if (sum == n) {
         System.out.println("从" + i + "开始到" + j + "有连续的数");
         num++;
        }
       }
      }
      if (num != 0) {
       System.out.println("连续的数有" + num + "种");
      } else {
       System.out.println("没有连续的数");
      }
     }
    

    如果大佬有更好的思路请指导

    展开全文
  • 题目:top-k算法,从n个大小的数组中,出k个最大的数字并输出 输入:数组大小n=10;k的值为5;数组为:9,8,3,2,10,20,13,1,5 输出:20,13,10,9,8 思路:1、维护k个最小堆,如果某个新进来的数字大于...
  • 给定一个长度为n-1的整形数组,数字的范围在1到n(无重复),其中有一个缺失的数字,写一段高效的程序出该数字。 一、数组有序 对于该数组是否有序,题目没有说明,假设有序,则可使用二分查找,时间复杂度为O...
  • Java实现 LeetCode 400 第N个数字

    万次阅读 多人点赞 2020-03-13 17:56:25
    400. 第N个数字 在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …中找到第 n 个数字。 注意: n 是正数且在32为整形范围内 ( n < 231)。 示例 1: 输入: 3 输出: 3 示例 2: 输入: 11 输出: 0 说明: 第11个...
  • 输入一行数字,其中有且只有一个数字出现了奇数次,其余数字均出现偶数次,出该数字并输出 运算关键:异或 从头到尾异或一遍,最后得到的那个数就是出现了奇数次的数。 因为,两次异或同一个数,结果不变,且...
  • 给出n个数,出这n个数的最大值,最小值,和。 问题描述 给出n个数,出这n个数的最大值,最小值,和。 输入格式 第一行为整数n,表示数的个数。 第二行有n个数,为给定的n个数,每个数的绝对值都小于10000。 输出...
  • # 从键盘上输入一个正整数n出1000至10000之间所有各位数字之和等于n的数 # 如输入32,则有9869满足要求。因为9869各位上数字之和等于32 用python解决,需要详细的代码和解释,谢谢
  • n 个无序整数( n&gt;10000), 则出其中最大的 M 个数字(5&lt; M&lt;10), 所需要的最小时间复杂度: 看了很多博客和论坛,这道题我找到了两种方法,在这里总结一下。 两种方法都用到了堆...
  • JAVA中输入任意N个数来得出最大值与最小值方法代码 方法 对任意键盘输入N个数的求最大值和最小值的方法有很多,一般都是对于N个数的比较,这里使用其中一种,排序法。 代码 java代码 import java.util.Arrays; ...
  • 题目描述:设计一个O(n^2)时间的算法,出由n个数字组成的序列的最长单调递增子序列。要求:(1)写出分析思路;(2)给出具体算法。 分析思路 从所给数组的第一个数开始,向后依次计算以此元素开始的最长单调...
  • 目录 1. 结论 2. 经典的几种解法 2.1 解法一:O(n*k) 2.2 解法二:O(n*logk) 2.3 解法三:O(n) ...2.4 解法四:O(n*logn+k) ...2.5 解法五:O(n*logn)...在N个乱序数字中查找第k大的数字,时间复杂度可以减小至O(N)。 ...
  • 【笔试题】出数组中重复的数字

    万次阅读 2018-08-04 21:48:34
    在一个数组长度为n的数组里,所有数字都在 0 ~ n-1 范围内,数组中某些数字是重复的,但不知道几个数字重复了,也不知道每个数字重复了多少次,请出数组中重复的数字。 思路一:插排思想(比较挫,时间复杂度:...
  • 给出n个数,出这n个数的最大值,最小值,和。 输入格式 第一行为整数n,表示数的个数。 第二行有n个数,为给定的n个数,每个数的绝对值都小于10000。 输出格式 输出三行,每行一个整数。第一行表示这些数中的最大...
  • 问题描述给出n个数,出这n个数的最大值,最小值,和。输入格式第一行为整数n,表示数的个数。第二行有n个数,为给定的n个数,每个数的绝对值都小于10000。输出格式输出三行,每行一个整数。第一行表示这些数中的...
  • 题目:在一个长度为n的数组里的所有数字都在0到n-1的范围内,出数组中任意一个重复的数字。 测试代码: public static void main(String[] args) { int [] numbers ={0,1,2,2,3,4,5}; int [] duplication = ...
  • ubuntu不到sysconfig i18n

    千次阅读 2013-12-31 09:23:57
    ubuntu关于i18n的配置文件在/etc/default文件夹的locale文件中
  • 抽象为比较直观的理解就是,一个数字最左边的 1 的左边一个 1 (大于 N 的最小的 2 的 N 次方),或者是最左边的1(小于N的最大的2的N次方),前提是这个数字本身不是2的n次方。 那么,如何呢?一种思路是,将...
  • 出数组中重复的数字-python版

    千次阅读 2019-07-05 20:30:59
    在一个长度为n的数组里有所有数字都在0~n-1的范围内,数组中某些数字是重复的,但不知道有几个数字重复了, 也不知道每个数字重复了几次,请出数组中任意一个重复的数字,例如,如果输入长度为7的数组 [ 2, 3, 1, ...
  • 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2...
  • n个数中出最小值(Python)

    万次阅读 2019-03-17 20:35:12
    n个数中出最小值,可以从第一个数a1开始依次作比较。首先比较a1和a2,将较小的一个与a3作比较;然后再将较小的一个与a4作比较……直到与an作比较,找到所有n个数中最小的值。用循环的方法求得最小值共要比较n-1...
  • 描叙:一大推数据里面,数字与数字之间用空格隔开,出出现次数最多的前N个。 #当数字之间的空格只有一个的时候 #sed 's/ /\n/g' data.txt | sort | uniq -c | sort -k1n -k2n | tail -10 > result.txt #存在的...
  • python-2.出数组中重复的数字

    千次阅读 2018-04-30 20:57:15
    在一个长度为n的数组里的所有数字都在0~n-1的范围内,数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请出数字中任意一个重复的数字。例如,如果输入长度为7的数字{2, 3, 1, 0, ...
  • c语言:N以内的所有素数

    万次阅读 多人点赞 2017-11-13 16:32:46
     我们已知2是最小素数,于是从2开始筛选(定义筛选的基数为n,此时n = 2)。那么所有的2的倍数都不是素数,  因为至少可以被2整除。之后对3、4、5、6.....进行筛选(此时n = 3、4、5、6、7.....)。   #include ...
  • 先用选第k大元素的方法选出第k大元素(具体可以参考选第k大元素的那篇BLOG),按Knuth的说法,时间开销是O(n),这样的话,如果我们找到第n-m大的元素,设其为a,然后顺序扫描一遍原序列,即可以得到最大的m个数,...
  • 如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大的那堆个数N大于10000个,继续对大堆快速排序一次分成2堆,如果大堆个数N小于10000个,就在小的那堆里面快速排序一次,第10000-n大的数字;...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 596,863
精华内容 238,745
关键字:

怎样找n字