假設我在 JavaScript 中有這個默認陣列：
const default = ['red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'violet']
我有用戶提供的這個陣列：
const user_arr = ['red', 'green', 'violet']
我需要比較這兩個陣列并驗證用戶陣列的順序是否正確（即我可以跳過級別，但不允許倒序）。
所以以下陣列是有效的：
['red', 'orange', 'violet']
['yellow', 'blue']
['green', 'indigo', 'violet']
有陣列將是無效的：
['red', 'violet', 'orange']
['green', 'violet', 'yellow]
如果不使用復雜的樹資料結構，這可能嗎？
uj5u.com熱心網友回復：
在這里，我將用戶陣列中的每個元素映射到正確陣列中的索引。
檢查索引陣列以確保它按升序排列。
請注意，“default”是一個 javascript 關鍵字，不是有效的變數名
const proper = ['red', 'orange', 'yellow', 'green', 'blue', 'indigo', 'violet']
const isValid = (arr) => {
const isAscending = (arr) => arr.every((el, i, a) =>
i === a.length - 1
? true
: el < a[i 1]
);
return isAscending(arr.map(el => proper.indexOf(el)));
}
const user_arr = ['red', 'green', 'blue']
console.log(isValid(user_arr));
console.log(isValid(['red', 'indigo', 'orange']));uj5u.com熱心網友回復：
我不知道這是否是最有效的方法，但這應該有效：
/**
*
* @param {string[]} ref
* @param {string[]} array
* @return {boolean}
*/
function checkValidity(ref, array) {
let prev = 0;
for (let i = 0; i < array.length; i ) {
const current = ref.findIndex((elt) => elt === array[i]);
if (current >= prev) prev = current;
else return false;
}
return true;
}
uj5u.com熱心網友回復：
此方法使用Map將專案的值映射到其在陣列中的索引。
然后使用該映射，我們檢查用戶提供的陣列中的每個元素是否在我們的原始陣列中具有該專案。如果沒有，則用戶陣列無效。如果它是已知項，我們需要獲取它在原始陣列中的位置，并檢查它是否大于我們檢查的前一個位置。如果是，則一切正常，如果不是，則用戶陣列無效。
解決方案備注
此解決方案在檢查 時不允許重復值<，而不是<=。如果您的原始陣列中有重復值，則該重復值的所有出現中的最后一次將確定其在陣列中的位置。目前這個實作不接受空陣列，但可以很容易地改變它，因此可以接受一個空陣列。
復雜
使用 Map 的優點是可以在O(1). 因此，需要O(n)時間n將原始陣列中的專案數初始化一次來初始化 Map。然后可以使用該 Map 來檢查用戶陣列在最壞情況下是否有效O(m)（例如，對于有效陣列），其中m是用戶提供的陣列中的專案數。僅使用陣列和方法，如indexOf()or find()，最壞情況下的時間復雜度為O(m * n). 對于像你這樣的小型陣列，這些事情并不重要。
const order = ["red", "orange", "yellow", "green", "blue", "indigo", "violet"];
const indexToValue = new Map();
order.forEach((item, idx) => indexToValue.set(item, idx));
const validArrays = [
["red"],
["red", "orange", "violet"],
["yellow", "blue"],
["green", "indigo", "violet"],
];
const invalidArrays = [
["red", "violet", "orange"],
["green", "violet", "yellow"],
];
/**
*
* @param {Array<string>} userArray
* @param {Map<string, number>} indexToValue
* @returns
*/
function checkCorrectness(userArray, indexToValue) {
if (!Array.isArray(userArray) || userArray.length === 0) return false;
let prev = -1;
return userArray.every((item) => {
// an unknown item is in the user array so it is invalid
if (!indexToValue.has(item)) return false;
// get index of the element in the original array
const idxInOrig = indexToValue.get(item);
// if the current index is smaller than the previous index -> invalid! stop immediately
if (idxInOrig < prev) return false;
// everything is fine current index is bigger than previous -> continue with next one
prev = idxInOrig;
return true;
});
}
console.log("Invalid arrays")
invalidArrays.forEach(invalid => console.log(checkCorrectness(invalid, indexToValue)));
console.log("Valid arrays")
validArrays.forEach(valid => console.log(checkCorrectness(valid, indexToValue)));轉載請註明出處，本文鏈接：https://www.uj5u.com/net/462133.html
標籤：javascript 数组 排序 等级制度
上一篇：冒泡排序串列的前四對