一、知识点:
数组、遍历
二、文字分析:
使用两个变量 count
和 candidate
分别表示当前候选牛种的计数和候选牛种。遍历数组时,如果 count
为0,表示当前没有候选牛种,我们将当前牛种设置为候选牛种,并将 count
设置为1。如果当前牛种与候选牛种相同,则将 count
加1;否则将 count
减1。最终,候选牛种一定是优势牛种。
复杂度分析:时间复杂度为 O(n),空间复杂度为 O(1)。
三、编程语言:
java
四、正确代码:
import java.util.*; public class Solution { /** * 找到优势牛种,即出现次数超过总数量一半以上的牛种 * * @param nums int整型一维数组,表示牛的种类数组 * @return int整型,优势牛种的种类 */ public int majority_cow(int[] nums) { int count = 0; // 当前候选牛种的计数 int candidate = 0; // 当前候选牛种 for (int num : nums) { if (count == 0) { candidate = num; count = 1; } else if (candidate == num) { count++; } else { count--; } } // 最终的候选牛种一定是优势牛种 return candidate; } }