整数数组之算法

frontoldman 发布于2019-08-23 11:37 / 1846人阅读

摘要：整数数组中只有一个重复的数字在一个长度为的数组里的所有数字都在到的范围内，数组中只有一个数字是重复的并且只重复一次，请找出数组中重复的数字。算法复杂度要求为。

整数数组中只有一个重复的数字

在一个长度为n的数组里的所有数字都在1到n的范围内，数组中只有一个数字是重复的并且只重复一次，请找出数组中重复的数字。算法复杂度要求为O(n)。

/**
 * 高斯求和
 * @param len        数组长度
 * @returns {number} 返回多余重复数字以外的总和
 */
function gauss(len) {
    return len * (len - 1) / 2
}

// 数组求和
function getSum(nums) {
    return nums.reduce((sum, num) => sum + num)
}

// 找重
function duplicate(nums) {
    const len = nums.length
    if (len <= 1) return false
    return getSum(nums) - gauss(len)
}

let numbers = [1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 10]
console.log(duplicate(numbers))    // 5

整数数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内，数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

/**
 * 把当前序列当成是一个下标和下标对应值是相同的数组
 * @param nums  数组
 * @returns {*} 重复数字的数组
 */
function duplicate(nums) {
    const len = nums.length
    if (len <= 1) return false
    let duplications = []
    for (let i = 0; i < len; i++) {
        if (nums[i] < 0 || nums[i] >= len) return false
        // 当前位的值和下标是不等时，则将当前位置 i 上的元素和 a[i] 位置上的元素比较
        while (nums[i] !== i) {
            if (nums[i] === nums[nums[i]]) {
                duplications.push(nums[i])
                break
            }
            // 当前位置 i 上的元素和 a[i] 位置上的元素不等时，则进行交换
            let temp = nums[i]
            nums[i] = nums[temp]
            nums[temp] = temp
        }
    }
    return duplications
}
let numbers = [2, 3, 6, 1, 5, 2, 3]
console.log(duplicate(numbers))

奇数在前，偶数在后

在一个长度为n的数组里的所有数字都在0到n-1的范围内，请将是数组中所有奇数排在偶数之前。算法复杂度要求为O(n)。

/**
 * 奇数在前，偶数在后
 * @param nums
 * @returns {*}
 */
function oddEven(nums) {
    let start = 0,
        end = nums.length - 1;
    while(start < end) {
        // 从下标为 start 开始，找到第一个偶数
        while(start < end && nums[start] % 2 === 1) {
            start++;
        }
        // 从下标为 end 开始，找到第一个奇数
        while(start < end && nums[end] % 2 === 0) {
            end--;
        }
        // 奇数与偶数交换
        let temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
    }
    return nums;
}
let nums = [9, 5, 4, 8, 6, 3, 2, 1, 7];
console.log(oddEven(nums));

GPU服务器私有云整数数组整数c语言数组大整数加法c语言算法 webrtc之vad算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/97231.html

深入理解HashMap(二): 关键源码逐行分析之hash算法

摘要：散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值，，，或的指纹。前言系列文章目录前面我们讨论了HashMap的结构, 接下来几篇我们从源码角度来看HashMap的实现细节. 本篇我们就来聊聊HashMap的hash算法本文的源码基于 jdk8 版本. hash算法上一篇文章我们提到, 为了利用数组索引进行快速查...

chunquedong 2019-08-19 10:50 评论0 收藏0
LeetCode 之 JavaScript 解答第41题 —— 缺失的第一个正数（First Mis

摘要：小鹿题目算法思路桶排序思想。再遍历数组，从下标开始判断该下标是否存放规定的数据，如果不是则该下标就是这组数据中缺失的最小正整数。桶排序还可以实现在一组数据中查找重复的数据。 Time：2019/4/6Title: First Missing PositiveDifficulty: DifficultyAuthor: 小鹿题目：First Missing Positive Give...

levius 2019-08-23 16:46 评论0 收藏0
#yyds干货盘点#看动画学算法之:hashtable

简介java中和hash相关并且常用的有两个类hashTable和hashMap,两个类的底层存储都是数组，这个数组不是普通的数组，而是被称为散列表的东西。散列表是一种将键映射到值的数据结构。它用哈希函数来将键映射到小范围的指数（一般为[0..哈希表大小-1]）。同时需要提供冲突和对冲突的解决方案。今天我们来学习一下散列表的特性和作用。文末有代码地址，欢迎下载。散列表的关键概念散列表中比较关键的三...

番茄西红柿 2021-11-22 14:56 评论0 收藏2637
看动画学算法之:hashtable

摘要：散列是一种算法通过散列函数，将大型可变长度数据集映射为固定长度的较小整数数据集。在讨论散列函数的实现之前，让我们讨论理想的情况完美的散列函数。对于标准二次探测冲突解决方法，当哈希表的时，插入可能失败。目录简介散列表的关键概念数组和散列表数组的问题 hash的问题线性探测二次探测双倍散列分离链接 ...

JessYanCoding 2021-11-22 12:03 评论0 收藏0
基本算法学习(四)之计数排序(JS)

摘要：计数排序首先我们要对计数排序有一个正确的认识计数排序是用于确定范围的整数的线性时间排序算法这一句话我们就可以知道计数排序该如何用了处理数据确定范围内的整数特点快线性时间其数据如下最佳情况最差情况平均情况计数排序的步骤如下查找待排序数组中最大计数排序首先我们要对计数排序有一个正确的认识,计数排序是用于确定范围的整数的线性时间排序算法,这一句话我们就可以知道计数排序该如何用了.处理数据...

AlexTuan 2019-08-21 11:22 评论0 收藏0