温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Leetcode 442 划水记录05

发布时间:2020-07-06 12:23:49 来源:网络 阅读:170 作者:hzChan 栏目:编程语言

题目:
**给定一个整数数组 a,其中1 ≤ a[i] ≤ n (n为数组长度), 其中有些元素出现两次而其他元素出现一次。

找到所有出现两次的元素。

你可以不用到任何额外空间并在O(n)时间复杂度内解决这个问题吗?

示例:

输入:
[4,3,2,7,8,2,3,1]

输出:
[2,3]**

看题目条件给的数据大小我就想用计数排序,但是怎么不申请额外空间呢?
其实完全可以利用每个元素的高位数据保存信息. 但是要确定要保存的信息的范围大小
比如你保存的是1-100 那你得给高8位留下来保存数据 底24位用来保存这个位置真实的数据值
leetcode上跑了还不错

int* findDuplicates(int* nums, int numsSize, int* returnSize) 
{
    //把每个元素的高16位和低16位分别保存2个信息点就可以了
    for (int m=0;m<numsSize;m++)
    {
        //每个元素的第16位才是其真正的值 因为高16位可能有其他值
        int realvalue = nums[m] &65535;//
        int high26 = nums[realvalue-1] >> 16;   //当前的数字  //取下高16位
        int g16 = high26; //如果不是空
        g16++;
        nums[realvalue -1] = (nums[realvalue - 1]&65535) | (g16<<16);
    }
    //申请额外空间保存返回结果这个应该不算额外空间吧
    int *result = malloc(sizeof(int)*numsSize);
    int cc = 0;
    for (int m = 0; m < numsSize; m++)
    {
        int high26 = (nums[m]>>16);
        if (2 == high26)
        {
            result[cc++] = m + 1;
        }
    //  printf("%d 出现%d次\n", m + 1, high26);
    }
    *returnSize = cc;
    return result;
}

时间
Leetcode 442 划水记录05

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI