logo标签列表

查找出现奇数次的元素

javascriptarraysfor-loopinteger
4
我正在尝试解决一个找出数组中出现奇数次的数字的练习。目前我已经做到了这一步，但输出结果却是一个出现偶数次的整数。例如，数字2出现了3次，数字4出现了6次，但输出结果是4，因为它被计算成出现了5次。为什么它会返回第一个发现的奇数集合呢？需要您的帮助！
         function oddInt(array) {
         var count = 0;
         var element = 0;
         for(var i = 0; i < array.length; i++) {
           var tempInt = array[i];
           var tempCount = 0;
             for(var j = 0; j <array.length; j++) {
                if(array[j]===tempInt) {
                tempCount++;
                  if(tempCount % 2 !== 0 && tempCount > count) {
                  count = tempCount; 
                  element = array[j];
                }
               }
              }
             }
           return element;
           }
           oddInt([1,2,2,2,4,4,4,4,4,4,5,5]);
你想要所有奇数还是只有一个？ - Schokokuchen Bäcker
只返回一个值！感谢您的回复。 - padawan
可能是计算JavaScript数组元素出现次数的重复问题。 - Dan Philip Bejoy
1
您有3个问题和0个被采纳的答案。拥有较低的被采纳答案率会让用户不愿意帮助您，因为您没有对我们付出的努力给予回报。 - Jorge Fuentes González
18个回答
9

function findOdd(numbers) {
  var count = 0;
  for(var i = 0; i<numbers.length; i++){
    for(var j = 0; j<numbers.length; j++){
      if(numbers[i] == numbers[j]){
        count++;
      }
    }
    if(count % 2 != 0 ){
      return numbers[i];
    }
  }
};

console.log(findOdd([20,1,-1,2,-2,3,3,5,5,1,2,4,20,4,-1,-2,5])); //5
console.log(findOdd([1,1,1,1,1,1,10,1,1,1,1])); //10

4

首先找到频率，然后找出哪些是奇数：

const data = [1,2,2,2,4,4,4,4,4,4,5,5]
const freq = data.reduce(
  (o, k) => ({ ...o, [k]: (o[k] || 0) + 1 }), 
  {})
const oddFreq = Object.keys(freq).filter(k => freq[k] % 2)

// => ["1", "2"]
你能进一步解释一下吗？看起来非常简洁。 - Gel
1
在 freq 表达式中，我们将项目数组折叠成频率字典（其中键是原始项目，值是该项出现的次数）。然后，我们过滤掉该字典的键，其相应值为奇数。 - Asad Saeeduddin
感谢@Asad。ES6语法使代码更简洁，如果不了解ES6，我可能无法理解它。这行代码({ ...o, [k]: (o[k] || 0) + 1 })创建了一个字典，对吗？ - Gel
@GelSisaed 对的，它会获取现有的字典 o，并添加另一个键 k，其值为 (o[k] || 0) + 1（即如果 k 存在于 o 中，则加上 1，否则加上 1 + 0）。 - Asad Saeeduddin
3
如果我们确定只有一个数字出现了奇数次，那么我们可以对这些数字进行异或操作，并在n次比较中找到出现奇数次的数字。两个二进制位进行异或操作时，如果它们不同，则为1，否则为0。如下是真值表：
A   B   A^B
0   0    0
0   1    1
1   0    1
1   1    0

当我们对所有数字进行异或运算时，最终的数字将是出现奇数次的数字。以一个数字为例，并将它与相同的数字（出现两次）进行异或运算。结果将为0，因为所有位都相同。 现在让我们将结果与同一个数字进行异或运算。现在结果将是那个数字，因为先前结果的所有位都是0，并且只有相同数字的设置位将在结果中设置。 现在将其扩展到n个数字的数组，出现偶数次的数字将给出结果0。数字出现奇数次将导致该数字成为最终结果中的数字。
func oddInt(numbers: [Int]) -> Int {
var result = 0
for aNumber in numbers {
  result = result ^ aNumber
}
return result
}
3
3

这里有一个O(N)或O(N*log(N))的解决方案

function findOdd(A) {
    var count = {};
    for (var i = 0; i < A.length; i++) {
        var num = A[i];
        if (count[num]) {
            count[num] = count[num] + 1;
        } else {
            count[num] = 1;
        }
    }
    var r = 0;
    for (var prop in count) {
        if (count[prop] % 2 != 0) {
            r = prop;
        }
    }
    return parseInt(r); // since object properies are strings
}
2

function oddInt(array) {
  // first: let's count occurences of all the elements in the array
  var hash = {};                 // object to serve as counter for all the items in the array (the items will be the keys, the counts will be the values)
  array.forEach(function(e) {    // for each item e in the array
    if(hash[e]) hash[e]++;       // if we already encountered this item, then increments the counter
    else hash[e] = 1;            // otherwise start a new counter (initialized with 1)
  });
  
  // second: we select only the numbers that occured an odd number of times
  var result = [];               // the result array
  for(var e in hash) {           // for each key e in the hash (the key are the items of the array)
    if(hash[e] % 2)              // if the count of that item is an odd number
      result.push(+e);           // then push the item into the result array (since they are keys are strings we have to cast them into numbers using unary +)
  }
  return result;
}
console.log(oddInt([1, 2, 2, 2, 4, 4, 4, 4, 4, 4, 5, 5]));

仅返回第一个：

function oddInt(array) {
  var hash = {};
  array.forEach(function(e) {
    if(hash[e]) hash[e]++;
    else hash[e] = 1;
  });
  
  for(var e in hash) { // for each item e in the hash
    if(hash[e] % 2)    // if this number occured an odd number of times
      return +e;       // return it and stop looking for others
  }
  // default return value here
}
console.log(oddInt([1, 2, 2, 2, 4, 4, 4, 4, 4, 4, 5, 5]));

1
这是因为每次找到奇数时，您都设置了element变量，因此在找到1、3和5的4时都进行了设置。
让我们逐步检查代码：
function oddInt(array) {
    // Set the variables. The count and the element, that is going to be the output
    var count = 0;
    var element = 0;

    // Start looking the array
    for(var i = 0; i < array.length; i++) {
        // Get the number to look for and restart the tempCount variable
        var tempInt = array[i];
        var tempCount = 0;
        console.log("");
        console.log(" * Looking for number", tempInt);
        // Start looking the array again for the number to look for
        for(var j = 0; j <array.length; j++) {
            // If the current number is the same as the one that we are looking for, sum it up
            console.log("Current number at position", j, "is", array[j]);
            if(array[j]===tempInt) {
                tempCount++;
                console.log("Number found. Current count is", tempCount);
                // Then, if currently there are an odd number of elements, save the number
                // Note that you are calling this altough you don't have looped throgh all the array, so the console will log 3 and 5 for the number '4'
                if(tempCount % 2 !== 0 && tempCount > count) {
                    console.log("Odd count found:", tempCount);
                    count = tempCount;
                    element = array[j];
                }
            }
        }
    }
    return element;
}
oddInt([1,2,2,2,4,4,4,4,4,4,5,5]);

我们想要做的是在遍历完整个数组后检查计数，方法如下：
function oddInt(array) {
    // Set the variables. The count and the element, that is going to be the output
    var count = 0;
    var element = 0;

    // Start looking the array
    for(var i = 0; i < array.length; i++) {
        // Get the number to look for and restart the tempCount variable
        var tempInt = array[i];
        var tempCount = 0;
        console.log("");
        console.log(" * Looking for number", tempInt);
        // Start looking the array again for the number to look for
        for(var j = 0; j <array.length; j++) {
            // If the current number is the same as the one that we are looking for, sum it up
            console.log("Current number at position", j, "is", array[j]);
            if(array[j]===tempInt) {
                tempCount++;
                console.log("Number found. Current count is", tempCount);
            }
        }
        // After getting all the numbers, then we check the count
        if(tempCount % 2 !== 0 && tempCount > count) {
            console.log("Odd count found:", tempCount);
            count = tempCount;
            element = tempInt;
        }
    }
    return element;
}
oddInt([1,2,2,2,4,4,4,4,4,4,5,5]);

顺便说一下，这只是让您了解问题所在并从中学习的方式，尽管这不是最优化的做法，因为您可能会注意到，当您已经得到所需输出时，您还需要寻找，比如说，数字2三次。如果性能是作业的一部分，那么您应该考虑另一种方式：P
非常感谢！真的帮了大忙！ - padawan
0
function oddOne (sorted) {
  let temp = sorted[0];
  let count = 0;
  for (var i = 0; i < sorted.length; i++) {
    if (temp === sorted[i]) {
      count++;
      if (i === sorted.length - 1) {
        return sorted[i];
      }
    } else {
      if (count % 2 !== 0) {
        return temp;
      }

      count = 1;
      temp = sorted[i];
    }
  }
}
0

"A" 是要被检查的数组。

function findOdd(A) {
    var num;
    var count =0;
    for(i=0;i<A.length;i++){
       num = A[i]
       for(a=0;a,a<A.length;a++){
          if(A[a]==num){
          count++;
          }
     } if(count%2!=0){
          return num;
     }
   }
}
0

之前我曾经为一个类似的问题实现过一种解决方案，以下是代码：

function findtheOddInt(A) {
let uniqueValues = [...new Set(A)]; // Get the unique values from array A
const odds = [];
uniqueValues.forEach(element => {
    const count = A.reduce((acc, cur) => cur === element ? acc + 1: acc, 0) // count the occurrences of the element in the array A
    if (count % 2 === 1) {
        odds.push(element);
    }
});
return odds[0]; // Only the first odd occurring element

}

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接