자바 어레이, 내장 찾기

자바 어레이, 내장 찾기

---

배열이 있고 있고 찾고 있습니다.

duplicates = false;
for(j = 0; j < zipcodeList.length; j++){
    for(k = 0; k < zipcodeList.length; k++){
        if (zipcodeList[k] == zipcodeList[j]){
            duplicates = true;
        }
    }
}

작동하지 않습니다. 그 이유는 무엇입니까?

---

코 대답에 ..

duplicates=false;
for (j=0;j<zipcodeList.length;j++)
  for (k=j+1;k<zipcodeList.length;k++)
    if (k!=j && zipcodeList[k] == zipcodeList[j])
      duplicates=true;

처음 질문에서 명확하지 않은 사용중인 어딘가를 읽었 거나 로 .equals()다시 전환하도록 편집 . 또한 실행 시간을 절반으로 줄이려면 설정 하지만 여전히 O (n ² )입니다.==intk=j+1

더 빠른 (한계) 방법

다음은 해시 기반 접근 방식입니다. 오토 박싱 비용을 지불해야하지만 O (n ² ) 대신 O (n )입니다. 진취적인 영혼은 원시적 인 int 기반 해시 세트를 것입니다 (Apache 또는 Google Collections에는 그런 것, methinks가 있습니다.)

boolean duplicates(final int[] zipcodelist)
{
  Set<Integer> lump = new HashSet<Integer>();
  for (int i : zipcodelist)
  {
    if (lump.contains(i)) return true;
    lump.add(i);
  }
  return false;
}

HuyLe에 활

몇 가지 추가 단계가 필요하다고 생각하는 다소 O (n) 솔루션에 대한 HuyLe의 답변 을 참조 하십시오.

static boolean duplicates(final int[] zipcodelist)
{
   final int MAXZIP = 99999;
   boolean[] bitmap = new boolean[MAXZIP+1];
   java.util.Arrays.fill(bitmap, false);
   for (int item : zipcodeList)
     if (!bitmap[item]) bitmap[item] = true;
     else return true;
   }
   return false;
}

아니면 그냥 그냥하게

static boolean duplicates(final int[] zipcodelist)
{
   final int MAXZIP = 99999;
   boolean[] bitmap = new boolean[MAXZIP+1];  // Java guarantees init to false
   for (int item : zipcodeList)
     if (!(bitmap[item] ^= true)) return true;
   return false;
}

상관이 있나?

글쎄요, 그래서 저는 약간의 벤치 마크를 실행했습니다. 그것은 모든 곳에서 불확실하지만 여기에 코드가 있습니다.

import java.util.BitSet;

class Yuk
{
  static boolean duplicatesZero(final int[] zipcodelist)
  {
    boolean duplicates=false;
    for (int j=0;j<zipcodelist.length;j++)
      for (int k=j+1;k<zipcodelist.length;k++)
        if (k!=j && zipcodelist[k] == zipcodelist[j])
          duplicates=true;

    return duplicates;
  }


  static boolean duplicatesOne(final int[] zipcodelist)
  {
    final int MAXZIP = 99999;
    boolean[] bitmap = new boolean[MAXZIP + 1];
    java.util.Arrays.fill(bitmap, false);
    for (int item : zipcodelist) {
      if (!(bitmap[item] ^= true))
        return true;
    }
    return false;
  }

  static boolean duplicatesTwo(final int[] zipcodelist)
  {
    final int MAXZIP = 99999;

    BitSet b = new BitSet(MAXZIP + 1);
    b.set(0, MAXZIP, false);
    for (int item : zipcodelist) {
      if (!b.get(item)) {
        b.set(item, true);
      } else
        return true;
    }
    return false;
  }

  enum ApproachT { NSQUARED, HASHSET, BITSET};

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    ApproachT approach = ApproachT.BITSET;

    final int REPS = 100;
    final int MAXZIP = 99999;

    int[] sizes = new int[] { 10, 1000, 10000, 100000, 1000000 };
    long[][] times = new long[sizes.length][REPS];

    boolean tossme = false;

    for (int sizei = 0; sizei < sizes.length; sizei++) {
      System.err.println("Trial for zipcodelist size= "+sizes[sizei]);
      for (int rep = 0; rep < REPS; rep++) {
        int[] zipcodelist = new int[sizes[sizei]];
        for (int i = 0; i < zipcodelist.length; i++) {
          zipcodelist[i] = (int) (Math.random() * (MAXZIP + 1));
        }
        long begin = System.currentTimeMillis();
        switch (approach) {
        case NSQUARED :
          tossme ^= (duplicatesZero(zipcodelist));
          break;
        case HASHSET :
          tossme ^= (duplicatesOne(zipcodelist));
          break;
        case BITSET :
          tossme ^= (duplicatesTwo(zipcodelist));
          break;

        }
        long end = System.currentTimeMillis();
        times[sizei][rep] = end - begin;


      }
      long avg = 0;
      for (int rep = 0; rep < REPS; rep++) {
        avg += times[sizei][rep];
      }
      System.err.println("Size=" + sizes[sizei] + ", avg time = "
            + avg / (double)REPS + "ms");
    }
  }

}

NSQUARED :

Trial for size= 10
Size=10, avg time = 0.0ms
Trial for size= 1000
Size=1000, avg time = 0.0ms
Trial for size= 10000
Size=10000, avg time = 100.0ms
Trial for size= 100000
Size=100000, avg time = 9923.3ms

HashSet 사용

Trial for zipcodelist size= 10
Size=10, avg time = 0.16ms
Trial for zipcodelist size= 1000
Size=1000, avg time = 0.15ms
Trial for zipcodelist size= 10000
Size=10000, avg time = 0.0ms
Trial for zipcodelist size= 100000
Size=100000, avg time = 0.16ms
Trial for zipcodelist size= 1000000
Size=1000000, avg time = 0.0ms

BitSet 사용

Trial for zipcodelist size= 10
Size=10, avg time = 0.0ms
Trial for zipcodelist size= 1000
Size=1000, avg time = 0.0ms
Trial for zipcodelist size= 10000
Size=10000, avg time = 0.0ms
Trial for zipcodelist size= 100000
Size=100000, avg time = 0.0ms
Trial for zipcodelist size= 1000000
Size=1000000, avg time = 0.0ms

BITSET이 이겼습니다!

그러나 .15ms는 currentTimeMillis()약간의 비용 만 있습니다. 100000보다 긴 목록의 경우, true간단히 긴 반환 할 수 있습니다 . 실질적인 목록이 임의의 것과 같은 경우 훨씬 더 짧은 목록에 실질적인 WHP를 반환 할 수 있습니다. 도덕은 무엇입니까? 한계에서 가장 용이 한 구현은 다음과 가변합니다.

 return true;

그리고 당신은 자주 틀리지 않을 것입니다.

---

알고리즘이 어떻게 작동하는지 보겠습니다.

an array of unique values:

[1, 2, 3]

check 1 == 1. yes, there is duplicate, assigning duplicate to true.
check 1 == 2. no, doing nothing.
check 1 == 3. no, doing nothing.
check 2 == 1. no, doing nothing.
check 2 == 2. yes, there is duplicate, assigning duplicate to true.
check 2 == 3. no, doing nothing.
check 3 == 1. no, doing nothing.
check 3 == 2. no, doing nothing.
check 3 == 3. yes, there is duplicate, assigning duplicate to true.

더 나은 알고리즘 :

for (j=0;j<zipcodeList.length;j++) {
    for (k=j+1;k<zipcodeList.length;k++) {
        if (zipcodeList[k]==zipcodeList[j]){ // or use .equals()
            return true;
        }
    }
}
return false;

---

큰 배열에서 더 나은 성능을 위해 비트 맵을 사용할 수 있습니다.

    java.util.Arrays.fill(bitmap, false);

    for (int item : zipcodeList)
        if (!bitmap[item]) bitmap[item] = true;
        else break;

업데이트 : 이것은 그날의 저의 매우 부주의 한 대답이며 참고 용으로 여기에 보관합니다. andersoj의 훌륭한 답변을 참조해야합니다 .

---

을 확인하려면 중복 서로 다른 쌍 을 비교해야 우리합니다 .

---

배열의 첫 번째 요소를 자신과 비교하고 있기 때문에이없는 곳이 있습니다.

---

k = j + 1을 초기화합니다. 요소를 자신과 비교하지 않고 비교도하지 않습니다. 예를 들어, j = 0, k = 1 및 k = 0, j = 1은 동일한 요소 집합을 비교합니다. 이 k = 0, j = 1 비교를 제거합니다.

---

하지 마십시오 사용 ==사용 .equals.

대신이를 시도하십시오 (IIRC, ZipCode가 Comparable작동을 구현해야합니다 .

boolean unique;
Set<ZipCode> s = new TreeSet<ZipCode>();
for( ZipCode zc : zipcodelist )
    unique||=s.add(zc);
duplicates = !unique;

---

Java에서 사용할 수 없습니다.

    for (String name : names)
    {         
      if (set.add(name) == false) 
         { // your duplicate element }
    }

add () 메서드를 사용하고 반환 값을 확인하십시오. add ()가 false를 반환하면 해당 요소가 Set에서 허용되지 않습니다.

---

public static ArrayList<Integer> duplicate(final int[] zipcodelist) {

    HashSet<Integer> hs = new HashSet<>();
    ArrayList<Integer> al = new ArrayList<>();
    for(int element: zipcodelist) {
        if(hs.add(element)==false) {
            al.add(element);
        }   
    }
    return al;
}

---

이 방법을 사용하는 것은 무엇입니까?

HashSet<Integer> zipcodeSet = new HashSet<Integer>(Arrays.asList(zipcodeList));
duplicates = zipcodeSet.size()!=zipcodeList.length;

---

@andersoj는 훌륭한 답변을 주지만 새로운 간단한 방법을 추가하고 싶습니다.

    private boolean checkDuplicateBySet(Integer[] zipcodeList) {
        Set<Integer> zipcodeSet = new HashSet(Arrays.asList(zipcodeList));
        if (zipcodeSet.size() == zipcodeList.length) {
            return true;
        }
        return false;
    }

zipcodeList가 int [] 인 경우 먼저 int []를 정수 []로 변환해야합니다 (자동 박싱이 아님). 여기 에 코드

완전한 완전한 코드는 다음과 가변적입니다.

    private boolean checkDuplicateBySet2(int[] zipcodeList) {
        Integer[] zipcodeIntegerArray = new Integer[zipcodeList.length];
        for (int i = 0; i < zipcodeList.length; i++) {
            zipcodeIntegerArray[i] = Integer.valueOf(zipcodeList[i]);
        }

        Set<Integer> zipcodeSet = new HashSet(Arrays.asList(zipcodeIntegerArray));
        if (zipcodeSet.size() == zipcodeList.length) {
            return true;
        }
        return false;
    }

도움이 되셨기를 바랍니다!

---

모든 두 요소를 인쇄하십시오. 반복되는 요소가 -1을 출력합니다 .

import java.util.*;

public class PrintDuplicate {

    public static void main(String args[]){
        HashMap<Integer,Integer> h = new HashMap<Integer,Integer>();


        Scanner s=new Scanner(System.in);
        int ii=s.nextInt();
        int k=s.nextInt();
        int[] arr=new  int[k];
        int[] arr1=new  int[k];
        int l=0;
        for(int i=0; i<arr.length; i++)
            arr[i]=s.nextInt();
        for(int i=0; i<arr.length; i++){
            if(h.containsKey(arr[i])){
                h.put(arr[i], h.get(arr[i]) + 1);
                arr1[l++]=arr[i];
            } else {
                h.put(arr[i], 1);
            }
        }
        if(l>0)
        { 
            for(int i=0;i<l;i++)
                System.out.println(arr1[i]);
        }
        else
            System.out.println(-1);
    }
}

---

import java.util.Scanner;

public class Duplicates {
    public static void main(String[] args) {
        Scanner console = new Scanner(System.in);
        int number = console.nextInt();
        String numb = "" + number;
        int leng = numb.length()-1;

        if (numb.charAt(0) != numb.charAt(1)) {
            System.out.print(numb.substring(0,1));
        }

        for (int i = 0; i < leng; i++){

          if (numb.charAt(i)==numb.charAt(i+1)){ 
             System.out.print(numb.substring(i,i+1));
          }
          else {
              System.out.print(numb.substring(i+1,i+2));
          }
       }
   }
}

참고 URL : https://stackoverflow.com/questions/3951547/java-array-finding-duplicates