成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

整數(shù)數(shù)組之算法

frontoldman / 1993人閱讀

摘要：整數(shù)數(shù)組中只有一個(gè)重復(fù)的數(shù)字在一個(gè)長(zhǎng)度為的數(shù)組里的所有數(shù)字都在到的范圍內(nèi)，數(shù)組中只有一個(gè)數(shù)字是重復(fù)的并且只重復(fù)一次，請(qǐng)找出數(shù)組中重復(fù)的數(shù)字。算法復(fù)雜度要求為。

整數(shù)數(shù)組中只有一個(gè)重復(fù)的數(shù)字

在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在1到n的范圍內(nèi)，數(shù)組中只有一個(gè)數(shù)字是重復(fù)的并且只重復(fù)一次，請(qǐng)找出數(shù)組中重復(fù)的數(shù)字。算法復(fù)雜度要求為O(n)。

/**
 * 高斯求和
 * @param len        數(shù)組長(zhǎng)度
 * @returns {number} 返回多余重復(fù)數(shù)字以外的總和
 */
function gauss(len) {
    return len * (len - 1) / 2
}

// 數(shù)組求和
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
整數(shù)數(shù)組中重復(fù)的數(shù)字

在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)，數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。

/**
 * 把當(dāng)前序列當(dāng)成是一個(gè)下標(biāo)和下標(biāo)對(duì)應(yīng)值是相同的數(shù)組
 * @param nums  數(shù)組
 * @returns {*} 重復(fù)數(shù)字的數(shù)組
 */
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
        // 當(dāng)前位的值和下標(biāo)是不等時(shí)，則將當(dāng)前位置 i 上的元素和 a[i] 位置上的元素比較
        while (nums[i] !== i) {
            if (nums[i] === nums[nums[i]]) {
                duplications.push(nums[i])
                break
            }
            // 當(dāng)前位置 i 上的元素和 a[i] 位置上的元素不等時(shí)，則進(jìn)行交換
            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))
奇數(shù)在前，偶數(shù)在后

在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)，請(qǐng)將是數(shù)組中所有奇數(shù)排在偶數(shù)之前。算法復(fù)雜度要求為O(n)。

/**
 * 奇數(shù)在前，偶數(shù)在后
 * @param nums
 * @returns {*}
 */
function oddEven(nums) {
    let start = 0,
        end = nums.length - 1;
    while(start < end) {
        // 從下標(biāo)為 start 開(kāi)始，找到第一個(gè)偶數(shù)
        while(start < end && nums[start] % 2 === 1) {
            start++;
        }
        // 從下標(biāo)為 end 開(kāi)始，找到第一個(gè)奇數(shù)
        while(start < end && nums[end] % 2 === 0) {
            end--;
        }
        // 奇數(shù)與偶數(shù)交換
        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));

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/97231.html

相關(guān)文章

  • 深入理解HashMap(二): 關(guān)鍵源碼逐行分析之hash算法

    摘要：散列函數(shù)把消息或數(shù)據(jù)壓縮成摘要，使得數(shù)據(jù)量變小，將數(shù)據(jù)的格式固定下來(lái)。該函數(shù)將數(shù)據(jù)打亂混合，重新創(chuàng)建一個(gè)叫做散列值，，，或的指紋。 前言 系列文章目錄 前面我們討論了HashMap的結(jié)構(gòu), 接下來(lái)幾篇我們從源碼角度來(lái)看HashMap的實(shí)現(xiàn)細(xì)節(jié). 本篇我們就來(lái)聊聊HashMap的hash算法 本文的源碼基于 jdk8 版本. hash算法 上一篇文章我們提到, 為了利用數(shù)組索引進(jìn)行快速查...

    chunquedong 評(píng)論0 收藏0

  • LeetCode 之 JavaScript 解答第41題 —— 缺失的第一個(gè)正數(shù)（First Mis

    摘要：小鹿題目算法思路桶排序思想。再遍歷數(shù)組，從下標(biāo)開(kāi)始判斷該下標(biāo)是否存放規(guī)定的數(shù)據(jù)，如果不是則該下標(biāo)就是這組數(shù)據(jù)中缺失的最小正整數(shù)。桶排序還可以實(shí)現(xiàn)在一組數(shù)據(jù)中查找重復(fù)的數(shù)據(jù)。 Time：2019/4/6Title: First Missing PositiveDifficulty: DifficultyAuthor: 小鹿 題目：First Missing Positive Give...

    levius 評(píng)論0 收藏0

  • #yyds干貨盤(pán)點(diǎn)#看動(dòng)畫(huà)學(xué)算法之:hashtable

    簡(jiǎn)介java中和hash相關(guān)并且常用的有兩個(gè)類(lèi)hashTable和hashMap,兩個(gè)類(lèi)的底層存儲(chǔ)都是數(shù)組，這個(gè)數(shù)組不是普通的數(shù)組，而是被稱(chēng)為散列表的東西。散列表是一種將鍵映射到值的數(shù)據(jù)結(jié)構(gòu)。它用哈希函數(shù)來(lái)將鍵映射到小范圍的指數(shù)（一般為[0..哈希表大小-1]）。同時(shí)需要提供沖突和對(duì)沖突的解決方案。今天我們來(lái)學(xué)習(xí)一下散列表的特性和作用。文末有代碼地址，歡迎下載。散列表的關(guān)鍵概念散列表中比較關(guān)鍵的三...

    番茄西紅柿 評(píng)論0 收藏2637

  • 看動(dòng)畫(huà)學(xué)算法之:hashtable

    摘要：散列是一種算法通過(guò)散列函數(shù)，將大型可變長(zhǎng)度數(shù)據(jù)集映射為固定長(zhǎng)度的較小整數(shù)數(shù)據(jù)集。在討論散列函數(shù)的實(shí)現(xiàn)之前，讓我們討論理想的情況完美的散列函數(shù)。對(duì)于標(biāo)準(zhǔn)二次探測(cè)沖突解決方法，當(dāng)哈希表的時(shí)，插入可能失敗。? 目錄 簡(jiǎn)介 散列表的關(guān)鍵概念 數(shù)組和散列表 數(shù)組的問(wèn)題 hash的問(wèn)題 線性探測(cè) 二次探測(cè) 雙倍散列 分離鏈接 ...

    JessYanCoding 評(píng)論0 收藏0

  • 基本算法學(xué)習(xí)(四)之計(jì)數(shù)排序(JS)

    摘要：計(jì)數(shù)排序首先我們要對(duì)計(jì)數(shù)排序有一個(gè)正確的認(rèn)識(shí)計(jì)數(shù)排序是用于確定范圍的整數(shù)的線性時(shí)間排序算法這一句話我們就可以知道計(jì)數(shù)排序該如何用了處理數(shù)據(jù)確定范圍內(nèi)的整數(shù)特點(diǎn)快線性時(shí)間其數(shù)據(jù)如下最佳情況最差情況平均情況計(jì)數(shù)排序的步驟如下查找待排序數(shù)組中最大 計(jì)數(shù)排序 首先我們要對(duì)計(jì)數(shù)排序有一個(gè)正確的認(rèn)識(shí),計(jì)數(shù)排序是用于確定范圍的整數(shù)的線性時(shí)間排序算法,這一句話我們就可以知道計(jì)數(shù)排序該如何用了.處理數(shù)據(jù)...

    AlexTuan 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<