C-输入1到n之间的n

Web程序数据库 Web程序数据库 主题:1214 回复:2505

C-输入1到n之间的n

想挽留 发布于 2016-10-23 字数 38 浏览 1058 回复 10

尽量优化时间复杂度和空间复杂度~

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

支持 Markdown 语法,需要帮助?

评论(10

清晨说ぺ晚安 2017-10-27 10 楼

方法1 (只针对n-1个数字的情况)
首先1-n求和得到sum(n)
然后把输入的n-1个数求和得到sum(n-1)

sum(n)-sum(n-1)就是你要的那个数。

方法2 初始化一个n长的数组,逐一将得到的n-1个数对应的数组下标的元素设置一个特殊值,最后检索数组,找到数组元素不是特殊值的下标,即可找到对应的缺失的数值

浮生未歇 2017-10-11 9 楼

import java.util.*;
public class Test {
/**

  • 最直观的办法
  • @param args
    */
    public static void main(String[] args) {
    int n=33;
    ArrayList<Integer> list=new ArrayList<Integer>();//1-n个数
    ArrayList<Integer> current=new ArrayList<Integer>();//n-1||n-2||n-.....不重复的数
    for(int i=1;i<=15;i++)
    current.add(i);//n-1||n-.....集合,具体可修改
    for(int i=1;i<=n;i++)
    list.add(i);
    list.removeAll(current);
    //打印
    for(Integer k:list)
    System.out.print(k+" ");
    }

}

这答案很久没更新了,有比这个更好的办法,我在别的问题里写过:
记缺少数的数组为c
比如有10000个数,缺少了一个,可以把c分成100组,那么就有101个节点。
记n为要比较的原数组的位置
从第一个节点开始遍历,与原数组n位置上进行比较,比较是否相同,相同则继续到下一个节点,如果不同,则说明前一个节点与当前节点中有缺少的数。
那么就从前一个节点的位置到当前节点的位置开始遍历,找出不同的位置,如果找到不同的位置则将n加一(实际意义是找到不同的位置,说明这个位置是缺少的数的位置,那么就将缺少的数放入,就相当于将比较原数组的位置+1),直到当前节点。
按以上操作,遍历到节点的末尾,比较c的长度+已经找出缺少的数的长度是否与原数组相同,如果相同则说明原数组后面没有缺少的数,如果不相同则说明原数组后面都是缺少的数。

偏爱自由 2017-09-29 8 楼

使用异或,缺少的一个和两个都能找到

甜柠檬 2017-08-26 7 楼

先排序,然后用二分法比较n/2 和 array[n/2]的值,以确定缺少的数字的位置,逐步缩小范围。
另k = array[n/2] - n/2;
如果 k = 2, 说明少的两个都在前面半区中。
k = 0, 少的两个都在后半区。
k = 1, 前后半区各少一个。

夜无邪 2017-05-25 6 楼

以下是最好的办法,不会导致溢出,同时时间复杂度为O(n),空间复杂度为O(1).
原理是 a^b^c=d;
a^b^d=c;
c就是缺少的那个元素。

int findloseelem(int s[],int n)
{
int subsum=1;
int sum=1;
for(int i=0;i<n-1;++i)
{//此处缺少一个元素,只有n-1个数
subsum=subsum^s[i];
}
for(int i=0;i<n;++i)
{//将 1到n全部异或
sum=sum^(i+1);
}

return sum^subsum;//结果就是这两个的异或值

}

瑾兮 2017-05-23 5 楼

我觉得用bitmap比较好

  1. 用一个n位bitmap,初始时各个位都为0,遍历数组存在的数将其对应位置1。
  2. 将得到的bitmap和111...111(n位)求异或即可得出确实的那两个数对应的位。

时间复杂度:O(n)
空间复杂度:O(n/8)

泛泛之交 2017-05-01 4 楼

对于第二题,想到一个好方式,理论上是O(1)复杂度
假设缺少的是a和b,并且a>b
首先使用方法一,确定缺少的两个数之和A(a+b=A)。通过A的数值,可以缩小范围。即缺少的两个数的组合情况(以A/2为中心向两侧进行探测)。
对于第二次探测,则是对数组再次遍历,当数据小于等于A/2时,做剑法,对于大于A/2时,做加法。这样的话,就能计算出缺少两个数据的差值B(a-b=B)。
注意,计算B的时候,需要根据A/2这个点向两边探测,即小于n-A和大于A的数据都不计算。

最后,就是计算一个二元一次方程了,就不多说了。

偏爱自由 2017-04-10 3 楼

存1到n之间的数,输入n-1个,直接算出1到n的总和,然后没输入一个数,就累加,最后减去就是缺少的那个数了
如果是缺少两个数的话,有两种思路,1、用大小为n的数组存n个数,n是动态的,所以可以考虑用vector,然后依次遍历即可,复杂度为o(n)
2、存储的时候构造一个大顶堆(额,好想是这个名字,就是中序遍历的时候是顺序的),这样可以根据根节点的值判断出所缺元素
希望对你有所帮助

想挽留 2017-02-02 2 楼

时间复杂度等于2n,需新增空间存储是char(n)。
1、建立一个char a[n]的数组。
2、依次循环,a[xxx]='1',这里xxx就是你1到n之间的整数。循环1次,不用排序,不用比较。
3、再循环依次,if a[i]!='1',输出i,就是缺少的那个数据。

甜柠檬 2016-10-24 1 楼

这个问题用异或的方法解, 无疑是最漂亮的. 缺少一个数字的解决方法, 那么缺少两个数字呢?

我在<<剑指Offer>>上看到类似的问题(面试题40). 说说大致思路, 怎么找缺失的两个数字.

把此n-2个数和 原来的n个数异或. 得到缺失的两个数(设为a, b)的异或值a^b.

因为a和b肯定不相等, 那么a^b中必定有为1的bit. 找出a^b中, 头一个为1的bit位, 假设为第i个bit. 也就是说a和b的第i个bit 不等.

接下来把 (此n-2个数和 原来的n个数) 按照第i位是否为1分为两组, 每组求异或, 则得到a和b.