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

frontoldman 發(fā)布于2019-08-23 11:37 / 1943人閱讀

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

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

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

/**
 * 高斯求和
 * @param len        數(shù)組長度
 * @returns {number} 返回多余重復數(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ù)組中重復的數(shù)字

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

/**
 * 把當前序列當成是一個下標和下標對應值是相同的數(shù)組
 * @param nums  數(shù)組
 * @returns {*} 重復數(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
        // 當前位的值和下標是不等時，則將當前位置 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))

奇數(shù)在前，偶數(shù)在后

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

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

GPU云服務器云服務器整數(shù)數(shù)組整數(shù)c語言數(shù)組大整數(shù)加法c語言算法 webrtc之vad算法

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

轉載請注明本文地址：http://systransis.cn/yun/97231.html

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

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

chunquedong 2019-08-19 10:50 評論0 收藏0
LeetCode 之 JavaScript 解答第41題 —— 缺失的第一個正數(shù)（First Mis

摘要：小鹿題目算法思路桶排序思想。再遍歷數(shù)組，從下標開始判斷該下標是否存放規(guī)定的數(shù)據(jù)，如果不是則該下標就是這組數(shù)據(jù)中缺失的最小正整數(shù)。桶排序還可以實現(xiàn)在一組數(shù)據(jù)中查找重復的數(shù)據(jù)。 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,兩個類的底層存儲都是數(shù)組，這個數(shù)組不是普通的數(shù)組，而是被稱為散列表的東西。散列表是一種將鍵映射到值的數(shù)據(jù)結構。它用哈希函數(shù)來將鍵映射到小范圍的指數(shù)（一般為[0..哈希表大小-1]）。同時需要提供沖突和對沖突的解決方案。今天我們來學習一下散列表的特性和作用。文末有代碼地址，歡迎下載。散列表的關鍵概念散列表中比較關鍵的三...

番茄西紅柿 2021-11-22 14:56 評論0 收藏2637
看動畫學算法之:hashtable

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

JessYanCoding 2021-11-22 12:03 評論0 收藏0
基本算法學習(四)之計數(shù)排序(JS)

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

AlexTuan 2019-08-21 11:22 評論0 收藏0