给你一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。编写一个程序,找出那个只出现了一次的元素。使用java编写
可以使用异或运算来解决这个问题。异或运算符(^)有以下规则:
因此,将数组中的所有元素进行异或运算,出现两次的元素会被抵消为0,只出现一次的元素会剩余。Java代码实现如下:
public int singleNumber(int[] nums) {
int result = 0;
for (int i = 0; i < nums.length; i++) {
result ^= nums[i];
}
return result;
}
这个方法的时间复杂度为O(n),因为需要遍历整个数组。
实验步骤
4-1
package sy3;
import java.util.Scanner;
/**
* @author
*
*/
public class Sy3_1 {
public static void main(String[] args) {
// TODO 自动生成的方法存根
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String[] words = s.split(" +");// 按照[+表示1个以上]空格区分
for (int i = 0; i < words.length; i++) {
char c = words[i].charAt(0);
if (c >= 'a' && c <= 'z') {// 小写字母
c = (char) (c - ('a' - 'A'));// 改成大写
}
String t = words[i].substring(1);// 其他字母
t.toLowerCase();// 全部小写
words[i] = c + t;
}
// 输出
for (int i = 0; i < words.length; i++) {
System.out.println(words[i]);
}
}
}
// 1.随机输入一组英语单词使用空格区分,编程实现所有单词的首字母大写其它小写并输出。
代码实现:
public class FindSingleElement {
public static void main(String[] args) {
int[] nums = {2, 2, 1, 3, 3, 4, 4, 5, 5};
int ans = findSingle(nums);
System.out.println(ans);
}
public static int findSingle(int[] nums) {
int ans = 0;
for (int num : nums) {
ans ^= num;
}
return ans;
}
}
解释:
该问题可以使用异或运算(XOR)来解决。异或运算的性质是当两个操作数不同时输出1,否则输出0。所以对同一个数异或两次,结果是这个数本身。换句话说,如果我们对所有数进行异或,则成对出现的数都被抵消了,最终剩余的就是只出现一次的数。
具体地,我们可以将数组中所有数进行异或操作,然后返回结果即可。
时间复杂度为O(n),空间复杂度为O(1)。