function findSmallestPositiveInteger(A) {
// sort array from smallest to largest number
A.sort((a, b) => a - b)
// remove duplicates because they just would take memory
const noDups =Array.from(new Set(A).keys())
let smallestPositiveInteger=1
let previous = noDups[0]
if(previous <= smallestPositiveInteger && previous>0)
smallestPositiveInteger
for(let i =1;i<noDups.length;i ){
const v = noDups[i]
if(previous > 0){
const diffWithPrevious = v - previous
// the logic for this early return is that we might not need to traverse
// the whole array for example imagine this example
// [1,2,5,6,8,...n]
// its clear that there is a gap between 5 and 2 so we can just
// conclude that 2 1 is the smallest postive integer not in our array
if(diffWithPrevious > 1) return previous 1;
}
// check if smallest positive integer in array is not 1
// if so return 1
if(previous == 0 && v > 1 ) return 1
if(v <= smallestPositiveInteger && v>0)
smallestPositiveInteger
previous = v
}
return smallestPositiveInteger
}
const arr =[-1,-2,1,3,10,9,3,2,3,3,10,2,7,99,100,10000,500,50,60,70,33]
console.log(findSmallestPositiveInteger(arr))
uj5u.com熱心網友回復：
將陣列中的整數放入查找結構中，然后嘗試從 開始的自然數，1直到找到不在陣列中的整數：
function findSmallestPositiveInteger(arr) {
const lookup = new Set(arr);
let i = 1;
while (lookup.has(i)) {
i ;
}
return i;
}
uj5u.com熱心網友回復：
我想我會按照以下方式進行。
- 對陣列進行排序，將每個元素視為一個數字（arr.sort 將其視為沒有比較函式的 strnig）
- 將目標變數設定為 1
- 遍歷元素，如果找到我的目標，增加我們現在尋找的數字
- 完成回圈后，回傳我們上次搜索的值
我想有點像這樣的東西。
"use strict";
window.addEventListener('load', onl oad, false);
function onLoad(evt)
{
let arr =[-1,-2,1,3,10,9,3,2,3,3,10,2,7,99,100,10000,500,50,60,70,33];
test(arr);
}
function test(arr)
{
arr = arr.sort(function(a, b){return a-b});
let nextTgt = 1;
arr.forEach( el => { if (el==nextTgt) nextTgt ;} );
console.log(arr);
console.log(nextTgt);
}編輯：如果正在檢查的當前陣列元素大于當前搜索目標，則回圈將中斷一個巨大的改進。
function test2(arr)
{
arr = arr.sort(function(a, b){return a-b});
let nextTgt = 1;
for (var i=0,n=arr.length; i<n; i )
{
if (arr[i] == nextTgt)
nextTgt ;
else if (arr[i]>nextTgt)
break;
}
console.log(arr);
console.log(nextTgt);
}
uj5u.com熱心網友回復：
const smallestPositiveInt = (arr) => {
// sort and remove negatives, duplicates, float
const sort = Array.from(new Set(arr))
.filter(n => n >= 1 && Number.isInteger(n))
.sort((a,b) => a - b);
let smallestInt = 1;
// if the smallest num isn't 1 we return 1 before any other check
if(sort[0] !== 1) {
return smallestInt
} else {
// add until you get to a positive int that doesn't exist in the arr, then return it
while(sort.includes(smallestInt)) {
smallestInt ;
}
return smallestInt
}
}
uj5u.com熱心網友回復：
您可以洗掉排序并構建一個物件，其中鍵是陣列中的值。然后只需遍歷陣列長度并在第一個丟失的數字處中斷。
function findSmallestPositiveInteger(A) {
const noDups = Object.assign({} , ...A.map((x) => ({[x]: true})));
let smallestPositiveInteger = 1
for (let i = 1; i < A.length; i ) {
if (typeof noDups[i] == 'undefined') {
smallestPositiveInteger = i;
break;
}
}
return smallestPositiveInteger;
}
const arr = [-1, -2, 1, 3, 10, 9, 3, 2, 3, 3, 10, 2, 7, 99, 100, 10000, 500, 50, 60, 70, 33]
console.log(findSmallestPositiveInteger(arr))
uj5u.com熱心網友回復：
實驗方法
這種方法以空間復雜性換取時間，但應該非常快。我們可以在 Javascript 中這樣做的原因是因為陣列可以像哈希一樣被濫用
const myArray = [-1,-2,1,3,10,9,3,2,3,3,10,2,7,99,100,10000,500,50,60,70,33, Infinity]
function findSmallestPositive(arr) {
// create a new array which uses the index
const indexed = Array(arr.length)
// add elements as the index of the new array
for (let i=0; i<arr.length; i ) {
if (arr[i] > 0) indexed[arr[i]] = 1
}
// return the first element above 0 that is missing
for (let i=1; i<indexed.length; i ) {
if (!indexed[i]) return i
}
// return undefined if nothing found
return undefined
}
console.time()
console.log(findSmallestPositive(myArray))
console.timeEnd()這里的想法是我們可以將陣列視為排序的哈希映射，然后我們只需要找到第一個索引是undefined.
注意：陣列可以根據內容、平臺和引擎以多種方式在后臺實作。V8以下是對引擎如何在內部處理陣列的深入探討：
https://ryanpeden.com/how-do-javascript-arrays-work-under-the-hood/#:~:text=In V8, if your array,by an array of% 20雙。
你現在有一個稀疏陣列。如果不是太空閑，它仍將由陣列支持，空陣列索引替換為“孔”值。如果您查看 V8 的 C 陣列源代碼（鏈接如下），您會看到對 element->is_the_hole(i) 的呼叫。如果陣列非常稀疏，它將不再由記憶體中的陣列支持。相反，它將由字典/哈希表支持，訪問元素和遍歷陣列都需要更長的時間。
uj5u.com熱心網友回復：
首先，過濾是 O(n)，因此任何像負數或非整數都是無關緊要的。在那之后，它最多可以是陣列的長度加一（并且您可以保證從一到該數字找到一個）。
您可以在 O(n) 中跟蹤其中的每一項：
const helper = arr => {
const marks = Array(arr.length 1).fill(false);
for (const n of arr) {
if (n < marks.length) marks[n - 1] = true;
}
return marks.findIndex(e => !e) 1;
};
const findSmallestPositiveInteger = arr => helper(arr.filter(e => Number.isInteger(e) && e > 0));
const arr = [-1, -2, 1, 3, 10, 9, 3, 2, 3, 3, 10, 2, 7, 99, 100, 10000, 500, 50, 60, 70, 33]
console.log(findSmallestPositiveInteger(arr))uj5u.com熱心網友回復：
這是一個不排序的解決方案，在 O(n) 中運行（它精確地掃描整個陣列兩次）并且不需要任何額外的臨時陣列。但它確實重新排列了原始陣列。
消除了將字串視為整數的isInteger可能性，就像 JavaScript 喜歡做的那樣，這就是示例回傳 5 的原因；該函式不認為字串'5'是整數。我認為這是正確的，但是 YMMV。
const myArray = [-1,-2,1,3,"5",10,9,3,2,3,4,10,2,7,99,100,10000,500,50,60,70,33, Infinity]
function findSmallestPositive(arr) {
for (let idx=0; idx<arr.length; idx ) {
const val = arr[idx];
if (Number.isInteger(val) && 0 <= val && val < arr.length) {
arr[idx] = arr[val-1];
arr[val-1] = val;
}
}
// At this point, the values are rearranged so that arr[i-1] is i
// if and only if i is in the array. Now scan again to find the
// smallest missing value.
for (let idx=1; idx<=arr.length; idx ) {
if (!(Number.isInteger(arr[idx-1]) && arr[idx-1] == idx)) {
return idx;
}
}
return arr.length 1;
}
console.time()
console.log(findSmallestPositive(myArray))
console.timeEnd()轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/490958.html
標籤：javascript 算法
上一篇：從另一個陣列創建一個陣列