【算法】求数组中出现了奇数次的一种/俩种数(异或运算)

左程云算法与数据结构课 https://www.bilibili.com/video/BV13g41157hK?p=2&spm_id_from=pageDriver

题目描述

在一个数组中,

(1)有一种数出现了奇数次,其余数出现了偶数次,求出现了奇数次的那种数。

(2)有俩种数出现了奇数次,其余数出现了偶数次,求出现了奇数次的俩种数。

题解

(1)一批数进行异或,与异或的顺序无关。

对数组的所有数进行异或,出现偶数次的数进行异或之后是0,出现奇数次的那种数异或之后还是那个数,所以最终异或结果是出现奇数次的那种数。

例如:数组[1,1,2,3,4,2,3,1,4]中除了1出现了奇数次外其余数均出现了偶数次,对数组元素进行异或,1^1^2^3^4^2^3^1^4=1^1^1^2^2^3^3^4^4=1

public static void printOddTimesNum1(int[] arr) {
    int eor = 0;
    for (int cur : arr) {
        eor ^= cur;
    }
    System.out.println(eor);
}

(2)假设出现了奇数次的俩种数分别是a和b。

对数组元素进行异或,最终结果是a^b。

由于a不等于b,故a^b的二进制中至少有一位为1,假设是第n位为1。

对数组中第n位为1的元素进行异或(以第n位是否为1,可以把数组分成两份,a和b分别落于这两份之中),则结果为出现了奇数次的俩种数中的一种,然后让它和a^b进行异或,则可以求出另一种出现了奇数次的数。

public static void printOddTimesNum2(int[] arr) {
    int eor1 = 0,eor2 = 0;
    for (int cur : arr) {
        eor1 ^= cur;
    }
    //eor!=0,其二进制中至少有一个位置为1,提取出最右的1
    int rightOne = eor1 & (~eor1+1);
    for (int cur : arr) {
        if ((cur & rightOne) == 1) {
            eor2 ^= cur;
        }
    }
    System.out.println(eor2 + " " + (eor1 ^ eor2));
}

推荐这些技术文章:

LG5795 [THUSC2015] 异或运算

摘要
给定长度为 \(n\) 的 \(\{a_i\}\) 和长度为 \(m\) 的 \(\{b_i\}\). 给定 \(u,d,l,r,k\), 求 \([u,d]\) 的 \(a_i\) 和 \([l,r]\) 的 \(b_i\) 自由组合, 得到所有 \(a_i\oplus b_i\) 中第 \(k\) 大的数字.

我们将 \(m\) 丢进 01 trie, 节点维护 \(cnt\). ...

寻找两个出现奇数次的数——异或的使用

题目:
已知在一批数组中,两个值出现了奇数次,其他值都出现了偶数次,快速找出出现奇数次的两个数
 
代码及注释解析:

1 public static void FindTwoOddTimes(int[] arr)
2 {
3 int ans1 = 0,ans2 = 0;
4 int eor = 0;
5 for (in...

数组八大运算

数组八大运算
1;冒泡排序
2;选择排序
3;直接插入排序
4;希尔排序
5;快速排序
6;归并排序
7;基数排序
8;堆排序
 
一  冒泡排序
原理;数组元素两两比较,交换位置,大元素向后放。那么经过一轮比较后做大的元素会出现在最大索引处
public class Outer { public static void main(String[] args) { ...

一维数组及其运算

## 一维数组
```java数组的定义: 数据类型 数组名[] = new 数据类型[大小]```
```java数组细节//1.数组是多个相同类型数据的组合,实现对这些数据的统一管理 int[] array1 = {1,34,678,54};//编译通过//2. 数组中的元素可以是任何数据类型,包括基本类型和 引用类型,但是不能混用 String[] a = {"...

位运算-求多个数中的个数为奇数的数

N个数中一个奇数
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[]={1,1,2,2,3,3,3};
int eof=0;
for(int i=0;i<sizeof(a)/sizeof(int);i++){
eof^=a[i];//偶数个数自己异或为零,剩下的...

得到数组的长度

int arr[] = {4, 3, 5, 2, 1, 3, 2, 3};
int n = sizeof( arr ) / sizeof( *arr );

 

...

整数类型不使用第三个元素交换两个元素的值

看排序算法的时候看到的

// 1.利用异或^
public void swap(int a, int b) {
a ^= b;
b ^= a;
a ^= b;
}

 

// 2.利用加减
public void swap(int a, int b) {
a = a + b;
b = a - b;
a = a - b;
}

&nbs...

在数组里找到唯一出现奇数次的数

package practice01;
//在数组里找到唯一出现奇数次的数
public class demo10 {
public static int oddNum(int[] arr){
int a=0;
for (int i=0;i<arr.length;i++){
a^=arr[i]; //a与所有数进行异或
...

位运算交换值、统计出现次数、交换位置(2022-02-02)

package demo;

public class P3q1 {

public static void main(String[] args) {
int a=5;
int b=10;

System.out.println("[a]"+a+"[b]"+b);
//三次异或,交换a、b的值
a=a^b; //a=a^b
b=a^b; //b=(a^b)^b...

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数在数组的前半部分,所有偶数在数组的后半部分。

常规解法(时空复杂度都是O(n))

class Solution {
public int[] exchange(int[] nums) {
int[] b=new int[nums.length];
int k=0;
for(int i=0;i<nums.length;i++)
{
if(n...

文章标题:【算法】求数组中出现了奇数次的一种/俩种数(异或运算)
文章链接:https://www.dianjilingqu.com/3961.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>