Announcement

Collapse
No announcement yet.

Tìm các giá trị khác nhau trong mảng

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Tìm các giá trị khác nhau trong mảng

    Chào mọi người!
    Có một đứa bạn hỏi mình một bài toán về mảng nhưng mình suy nghĩ mãi mà không ra nên mình muốn nhờ sự giúp đỡ của mọi người. Bài toán như sau:
    Cho một mảng số nguyên lớn (khoảng 1 triệu phần tử), các giá trị trong mảng có thể lặp lại nhiều lần. Yêu cầu tìm và in ra tất cả khác giá trị khác nhau trong mảng (không cho phép sử dụng 2 vòng lặp lồng nhau).
    Mới đầu thì mình làm theo phương pháp sắp xếp mảng tăng dần rồi sau đó duyệt mảng để in ra kết quả. Nhưng mà tất cả các thuật toán sắp xếp đều sử dụng 2 vòng lặp lồng nhau nên đến bây giờ mình vẫn chưa có cách để giải quyết bài này.
    Mong mọi người giúp mình tìm lời giải.:salute:

  • #2
    Originally posted by 11520318 View Post
    Chào mọi người!
    Có một đứa bạn hỏi mình một bài toán về mảng nhưng mình suy nghĩ mãi mà không ra nên mình muốn nhờ sự giúp đỡ của mọi người. Bài toán như sau:
    Cho một mảng số nguyên lớn (khoảng 1 triệu phần tử), các giá trị trong mảng có thể lặp lại nhiều lần. Yêu cầu tìm và in ra tất cả khác giá trị khác nhau trong mảng (không cho phép sử dụng 2 vòng lặp lồng nhau).
    Mới đầu thì mình làm theo phương pháp sắp xếp mảng tăng dần rồi sau đó duyệt mảng để in ra kết quả. Nhưng mà tất cả các thuật toán sắp xếp đều sử dụng 2 vòng lặp lồng nhau nên đến bây giờ mình vẫn chưa có cách để giải quyết bài này.
    Mong mọi người giúp mình tìm lời giải.:salute:
    Em dùng thuật toán đếm ở đây http://forum.uit.edu.vn/threads/5412...l=1#post321521 - 1 vòng lặp rồi sau đó in ra những số có SL > = 1

    Comment


    • #3
      Originally posted by 11520318 View Post
      Chào mọi người!
      Có một đứa bạn hỏi mình một bài toán về mảng nhưng mình suy nghĩ mãi mà không ra nên mình muốn nhờ sự giúp đỡ của mọi người. Bài toán như sau:
      Cho một mảng số nguyên lớn (khoảng 1 triệu phần tử), các giá trị trong mảng có thể lặp lại nhiều lần. Yêu cầu tìm và in ra tất cả khác giá trị khác nhau trong mảng (không cho phép sử dụng 2 vòng lặp lồng nhau).
      Mới đầu thì mình làm theo phương pháp sắp xếp mảng tăng dần rồi sau đó duyệt mảng để in ra kết quả. Nhưng mà tất cả các thuật toán sắp xếp đều sử dụng 2 vòng lặp lồng nhau nên đến bây giờ mình vẫn chưa có cách để giải quyết bài này.
      Mong mọi người giúp mình tìm lời giải.:salute:
      Nếu giá trị của mỗi phần tử là nhỏ thì em tham khảo link trên của thầy Toàn. Còn nếu giá trị các phần tử là lớn thì em nên ném nó vào một cái cây nhị phân tìm kiếm cân bằng hay một cái bảng băm em nhé.
      Last edited by truonganpn; 15-05-2015, 22:57.

      Comment


      • #4
        Ủa? 1000.000 phần tử, mình dùng thuật toán sắp xếp nhanh chỉ với O(N*log(N)) thôi mà anh.
        Với lại nếu dùng đếm phân phối thì phải tùy vào giới hạn của a[i] nữa.

        Comment


        • #5
          Originally posted by 15520197 View Post
          Ủa? 1000.000 phần tử, mình dùng thuật toán sắp xếp nhanh chỉ với O(N*log(N)) thôi mà anh.
          Với lại nếu dùng đếm phân phối thì phải tùy vào giới hạn của a[i] nữa.
          sắp xếp nhanh thì không phù hợp yêu cầu đề rồi mà.

          Comment


          • #6
            Originally posted by 15520197 View Post
            Ủa? 1000.000 phần tử, mình dùng thuật toán sắp xếp nhanh chỉ với O(N*log(N)) thôi mà anh.
            Với lại nếu dùng đếm phân phối thì phải tùy vào giới hạn của a[i] nữa.
            theo mình nghĩ thì nếu sort mảng xong thì cũng đâu có ra vân đề, còn phải xóa mấy cái giống nhau nữa mà. Lại tốn 1 vòng for

            Comment


            • #7
              Sao lại không phù hợp với yêu cầu đề ra anh? Miễn độ phức tạp máy vẫn còn chạy được mà.

              Comment


              • #8
                Sort mảng xong, cho chạy từ đầu đến cuối mảng vẫn đếm được số phần tử khác nhau chứ ạ! 1 vòng for nữa thì sao đâu? Độ phức tạp thuật toán vẫn có thể máy còn chạy được.

                Comment


                • #9
                  Originally posted by 15520197 View Post
                  Sao lại không phù hợp với yêu cầu đề ra anh? Miễn độ phức tạp máy vẫn còn chạy được mà.
                  người đặt vấn đề có nhắc đến độ phức tạp đâu, người ta chỉ cho biết yêu cầu là: "(không cho phép sử dụng 2 vòng lặp lồng nhau)"

                  Comment


                  • #10
                    Thử cái này coi.(chưa Test)

                    public void InMang(int[] inputs)
                    {
                    var outputs = new List<int>();
                    foreach (var input in inputs)
                    {
                    if (!outputs.Contains(input))
                    {
                    outputs.Add(input);
                    }
                    }
                    foreach (var output in outputs)
                    {
                    Console.WriteLine(output);
                    }
                    }

                    Comment


                    • #11
                      Originally posted by 10520067 View Post
                      public void InMang(int[] inputs)
                      {
                      var outputs = new List<int>();
                      foreach (var input in inputs)
                      {
                      if (!outputs.Contains(input))
                      {
                      outputs.Add(input);
                      }
                      }
                      foreach (var output in outputs)
                      {
                      Console.WriteLine(output);
                      }
                      }
                      foreach (var input in inputs)
                      {
                      if (!outputs.Contains(input))
                      {
                      outputs.Add(input);
                      }
                      }

                      anh chuyển vào thế này thì nhìn ngoài nó như 1 vòng lặp thôi, nhưng thực tế thì bên trong đâu chỉ đơn thuần là 1 vòng lặp đâu. rõ ràng là "if (!outputs.Contains(input))" có chứa vòng lặp mà.
                      Last edited by 14520820; 07-01-2016, 17:26.

                      Comment


                      • #12
                        Originally posted by 14520820 View Post
                        foreach (var input in inputs)
                        {
                        if (!outputs.Contains(input))
                        {
                        outputs.Add(input);
                        }
                        }

                        anh chuyển vào thế này thì nhìn ngoài nó như 1 vòng lặp thôi, nhưng thực tế thì bên trong đâu chỉ đơn thuần là 1 vòng lặp đâu. rõ ràng là "if (!outputs.Contains(input))" có chứa vòng lặp mà.
                        Nói như em thì hàm so sánh chuỗi cũng có vòng lặp

                        Comment


                        • #13
                          Originally posted by 10520067 View Post
                          Nói như em thì hàm so sánh chuỗi cũng có vòng lặp
                          Đề là mảng số nguyên mà chuỗi đâu ra em

                          Comment


                          • #14
                            Originally posted by truonganpn View Post
                            Đề là mảng số nguyên mà chuỗi đâu ra em
                            ak. chưa hiểu ý rồi.
                            Ý là nếu hàm so sánh 2 chuỗi cũng được gọi là có vòng lặp trong trường hợp trên thì hàm contrains trên List cũng có vòng Lặp.
                            string a = "abc";
                            string b = "cde";
                            if (a.Contains(b))
                            {
                            return true;
                            }
                            như ví dụ trên thì được gọi là có vòng lặp không ?.

                            Comment


                            • #15
                              Originally posted by 10520067 View Post
                              Nói như em thì hàm so sánh chuỗi cũng có vòng lặp
                              Originally posted by 10520067 View Post
                              ak. chưa hiểu ý rồi.
                              Ý là nếu hàm so sánh 2 chuỗi cũng được gọi là có vòng lặp trong trường hợp trên thì hàm contrains trên List cũng có vòng Lặp.
                              string a = "abc";
                              string b = "cde";
                              if (a.Contains(b))
                              {
                              return true;
                              }
                              như ví dụ trên thì được gọi là có vòng lặp không ?.
                              ý của em là anh lưu nó trong list thì khi anh tìm kiếm một phần tử trong list anh sẽ tốn ít nhất một vòng lặp để xem nó có ở trong đó hay không.
                              cho dù với ý tưởng đó anh không dùng contains trong list của c# thì nó cũng phải tốn vòng lặp thôi.
                              Last edited by 14520820; 07-01-2016, 21:04.

                              Comment

                              LHQC

                              Collapse
                              Working...
                              X