整數數組之算法

frontoldman 發布于2019-08-23 11:37 / 1937人閱讀

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

整數數組中只有一個重復的數字

在一個長度為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算法

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/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