我编写了一种递归方法,用于查找数组中不重复的单个项目(而所有其他项目都是成对且彼此相邻的)。。我的问题是,这是否可以在没有递归的情况下完成(也许使用 while 循环),并且在函数中使用循环比仅使用递归更有效(就内存而言)?
当前解决方案:
function findSingularElement(arr, low, high) {
// base cases
if (arr.length < 3) return console.log('Invalid length of array.');
if (low > high) return;
if (low == high) return console.log(arr[low]);
var mid = low + (high - low) / 2;
if (mid % 2 === 0) {
if (arr[mid] == arr[mid + 1]) {
return findSingularElement(arr, mid + 2, high);
} else {
return findSingularElement(arr, low, mid);
}
} else {
if (arr[mid] == arr[mid - 1]) {
return findSingularElement(arr, mid + 1, high);
} else {
return findSingularElement(arr, low, mid - 1);
}
}
}
var array = [1, 1, 3, 3, 4, 5, 5, 7, 7, 8, 8];
谢谢。
最佳答案
要从函数中删除递归,只需用适当的变量赋值替换递归调用即可:
function findSingularElement1(arr) {
if (arr.length < 3)
throw('Invalid length of array.');
var low = 0, high = arr.length - 1;
while (low < high) {
var mid = low + (high - low) / 2;
if (mid % 2 === 0) {
if (arr[mid] == arr[mid + 1]) {
low = mid + 2;
} else {
high = mid;
}
} else {
if (arr[mid] == arr[mid - 1]) {
low = mid + 1;
} else {
high = mid - 1;
}
}
}
return low == high ? arr[low] : null;
}
也就是说,您的整个方法似乎过于复杂,您可以通过简单的循环轻松找到未配对的项目:
for (var i = 0; i < array.length; i += 2)
if (array[i] != array[i + 1])
return array[i];
(假设数组已排序,并且每个项目恰好出现一次或两次)。
关于javascript - JS 数组二分查找中的递归与无递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39583376/